A = [
1256681 1127287 1964802 1167163 1098867 1027452 1008775 1024798 1133780 1101540 1268645 1198758 1316815 1536212 1734007 2049335 2243250 2371470 2372124 2360181 2104880 1832856 1687581 1635272 1650706 1985262 2010569 2021305 2192836 1864985 1854780 1757060 1458229 1490650 1443329 1460350 1463272 1349015 1357016 1330914 1299369 1321533 1322503 1370651 1429355 1401382 1411178 1400042 1402220 1402915 1336043 1348045 1404962 1397510 1395886 1421881 1404807 1412115 1376145 1324921 1311161 1306978 1313185 1323692 1355848 1403103 1397304 1388281 1379069 1359166 1333715 1334463 1356606 1359183 1376799 1399460 1407823 1386029 1373809 1345936 1315375 1313411 1286293 1292131 1306058 1302180 1288739 1267774 1261808 1243984 1223958 1212488 1208667 1201800 1202582 1206423 1197903 1197077 1195759 1170199 1156600 1149151 1135052 1127366 1131629 1137159 1131306 1131152 1127156 1116284 1102017 1091677 1083362 1078719 1075997 1073611 1084455 1080537 1074352 1064673 1058057 1049141 1036510 1029182 1026429 1024397 1022911 1019997 1016220 1012105 1001973 995752 988139 979914 972116 968458 959812 958876 959126 950004 947125 937306 929689 923056 914920 910562 908338 908553 906963 907319 905481 895239 892865 879632 870370 864978 860046 856462 851253 849251 842266 836901 828442 823274 817357 814212 808497 805935 801997 801399 795611 790753 786843 782067 775781 770492 765544 761063 759377 754833 752353 748058 743608 742188 734904 731116 726221 721412 719613 715699 713347 709810 708347 704967 701249 697413 694369 690458 687734 686399 681969 680176 677938 672983 669738 663453 661191 659479 652277 647497 644962 641143 633848 631218 625511 620461 614226 611274 609921 605342 606152 604149 599799 602045 594990 590749 584834 579691 574464 569594 563524 560272 556416 551868 547565 544205 539058 536504 532376 525560 523081 519827 517447 513263 510906 508092 504410 501775 496937 492359 488203 484528 482390 479447 476496 472454 470347 466790 463572 458504 454717 452994 449740 444773 443495 438892 435820 434283 429414 426698 422683 418950 416444 414072 408939 406178 403640 401471 397583 393541 391079 387486 382487 382018 378190 375430 372785 369667 366885 363618 360419 355814 352793 351398 348349 345472 341881 339195 336675 333870 330549 326450 322936 318578 316912 313346 311668 309032 305600 303596 299673 296376 291977 289408 286924 284587 280328 277171 275953 273474 269636 266262 263581 260166 256623 253175 251849 248427 246692 242966 241257 237700 235034 232044 228238 225690 222909 220477 217276 214508 211898 209605 206724 203017 200727 197995 195921 192804 190775 188240 185140 182759 180109 177974 174844 171875 168717 167254 164039 162587 159400 157776 155575 153326 150102 146859 145441 142845 140954 138810 135791 133486 131622 128927 127410 125544 122733 120638 118433 116333 114040 112504 110262 108248 106431 104654 102718 100454 98433 97431 95391 93995 92092 90403 88656 86247 85113 82898 81443 80170 78552 77097 75637 74185 72477 71039 69421 68118 66637 65332 63512 62311 61044 59537 58926 57047 55660 55014 53924 52544 51653 50114 48800 48124 46993 45896 44687 44117 43197 41606 41066 40171 38881 38047 37577 36684 35366 35330 34032 32944 32602 31688 30731 30295 29519 29070 28410 27440 26866 26072 25475 25025 24304 23504 23163 22728 22082 21775 20777 20503 19984 19375 18802 18554 18046 17650 17351 16625 16175 15922 15176 15240 14685 14432 14012 13609 13341 12943 12766 12299 12146 11793 11565 11191 10915 10636 10363 9945 9789 9474 9207 9033 8672 8353 8274 7971 7700 7672 7517 7389 7153 6814 6905 6601 6264 6293 6324 6032 5926 5587 5235 5403 5208 5024 4966 4714 4655 4574 4432 4279 4136 4079 3950 3926 3832 3705 3599 3490 3426 3207 3308 3096 3169 3107 2876 2799 2861 2747 2608 2588 2449 2407 2437 2409 2320 2267 2193 2148 2037 2011 1933 1854 1940 1828 1801 1755 1686 1699 1620 1551 1524 1519 1500 1459 1434 1364 1361 1339 1313 1251 1204 1241 1217 1199 1113 1147 1074 1065 1080 1018 1053 1012 920 917 918 925 849 859 860 774 843 811 809 742 768 764 673 750 718 681 682 673 689 687 646 637 605 599 603 606 581 617 571 557 547 534 546 526 515 531 543 458 453 529 479 502 440 458 456 460 441 411 426 431 402 406 477 394 431 407 426 408 376 404 386 381 359 361 378 372 357 342 321 370 365 364 356 355 337 373 356 321 341 310 334 348 322 332 326 292 308 310 302 311 317 286 277 300 282 282 282 294 301 327 273 289 283 274 279 291 294 283 231 267 266 275 269 270 260 267 273 243 244 254 260 274 239 225 265 228 245 252 232 261 245 233 249 268 229 253 257 205 243 204 253 219 196 199 209 234 209 203 208 248 222 222 219 200 229 202 208 181 192 193 244 204 190 207 176 182 198 220 204 169 204 209 194 194 179 157 200 208 192 175 181 176 188 183 190 175 182 169 173 186 164 165 155 172 173 161 157 177 177 173 168 154 160 153 175 166 167 171 163 165 186 154 153 166 140 135 140 155 149 168 159 146 159 146 147 136 149 135 151 150 128 127 138 135 146 138 153 148 140 150 156 141 128 128 115 120 156 134 169 131 140 128 143 116 149 112 112 148 134 144 116 122 118 130 142 130 132 122 122 107 115 120 111 89 128 150 115 107 103 102 129 120 107 117 87 105 109 95 111 105 116 111 110 105 97 104 90 103 103 96 97 125 97 95 118 94 129 110 113 101 91 88 109 108 114 93 114 120 98 93 80 77 68 76 82 106 82 88 97 100 88 94 77 77 87 104 75 79 71 86 87 92 75 77 99 94 81 100 88 81 105 85 60 75 73 104 96 81 71 74 88 74 77 90 62 84 69 57 76 78 80 76 91 77 82 86 79 86 72 75 79 76 66 70 71 63 58 63 71 66 63 79 67 74 62 68 65 71 60 76 67 75 68 64 74 69 56 53 67 65 60 58 65 61 57 55 66 65 62 64 58 47 70 66 55 50 51 58 54 64 56 51 47 43 50 75 49 67 56 43 53 58 54 54 46 56 64 54 57 49 56 57 63 59 55 55 39 38 53 55 52 70 56 64 45 44 49 42 53 53 43 47 50 44 49 53 63 49 60 52 37 44 48 37 44 42 51 47 51 54 44 46 55 39 40 40 45 48 32 32 38 47 43 27 39 36 30 31 47 49 39 42 32 43 49 29 41 43 65 35 46 43 53 41 39 32 35 40 40 35 41 29 27 30 28 34 44 42 38 35 30 34 36 33 44 41 29 35 38 32 33 25 38 30 32 40 48 24 35 42 34 34 50 21 30 41 34 36 44 39 24 24 25 27 33 33 25 27 30 21 22 39 27 39 28 31 33 32 26 25 24 22 37 28 28 29 35 31 29 26 28 32 35 32 23 32 28 30 23 32 18 30 30 25 18 27 20 17 26 27 33 16 22 27 28 19 25 33 20 20 24 28 25 25 28 18 24 21 16 17 24 20 28 28 20 27 16 27 21 25 17 20 23 15 16 20 17 20 17 19 28 24 20 26 25 22 15 24 17 24 19 22 25 18 26 17 18 19 20 25 31 21 28 33 25 17 15 34 25 10 21 18 38 36 26 45 17 13 17 26 30 18 30 27 16 21 14 23 35 16 25 19 38 26 18 14 12 15 15 18 18 21 28 13 15 14 17 19 12 16 18 15 15 22 13 18 16 9 15 6 20 18 16 14 16 18 14 10 13 14 16 14 11 14 22 11 8 13 15 15 7 14 12 15 15 11 16 23 12 8 9 12 17 13 7 16 11 10 15 6 13 12 5 11 7 12 9 7 5 12 11 10 9 5 9 8 11 13 11 8 7 9 14 4 12 15 5 10 6 8 15 6 9 7 12 11 8 11 7 7 6 6 7 11 6 12 10 9 12 7 8 12 15 6 12 16 13 11 13 11 9 10 12 9 5 14 15 12 8 5 13 10 10 7 8 12 6 8 12 14 17 11 13 8 10 26 10 15 12 35 21 17 20 24 29 9 8 14 23 22 30 13 21 14 19 17 8 19 32 39 10 20 9 22 16 21 17 35 17 63 33 15 10 13 19 4 15 9 17 46 66 13 23 22 23 19 7 8 9 6 8 5 7 9 9 4 11 9 9 4 7 6 4 11 9 5 4 4 9 4 12 12 8 11 9 9 8 2 5 11 9 10 10 11 9 6 12 6 6 23 13 55 12 14 15 37 37 20 21 9 9 17 6 6 5 51 26 7 22 8 13 24 4 7 5 13 7 17 3 13 29 15 11 10 4 14 25 7 7 10 7 28 11 7 6 41 19 9 14 5 5 5 14 7 13 8 5 7 7 4 7 6 8 6 5 5 1 6 6 4 4 10 5 10 5 6 5 6 7 5 6 8 5 4 5 9 8 6 4 4 6 4 6 5 4 9 5 6 4 8 11 6 5 5 11 5 8 6 7 4 5 3 5 6 6 10 3 6 7 5 6 7 4 4 5 11 8 4 5 5 5 5 6 4 4 3 4 5 3 2 3 4 8 7 7 5 6 6 4 4 3 12 8 5 6 6 6 7 6 6 5 3 2 4 4 5 11 2 2 5 6 7 6 5 6 11 6 4 6 6 6 5 8 6 4 0 9 2 5 0 5 2 3 7 4 6 5 2 7 6 1 5 3 5 2 2 5 3 5 3 4 5 4 6 6 3 4 2 4 5 3 9 8 2 3 4 4 3 1 5 6 1 5 3 2 3 5 2 6 1 4 6 6 3 4 3 5 4 2 7 1 7 3 5 4 1 1 3 0 3 4 4 2 4 1 0 2 5 5 2 4 3 5 2 3 2 2 2 1 1 5 3 4 3 1 1 3 2 5 1 2 8 1 3 4 2 1 4 1 4 1 2 7 1 4 1 1 2 3 2 1 6 4 3 4 3 4 1 2 1 0 0 2 1 0 2 0 5 2 3 1 2 1 3 1 1 3 1 4 2 3 1 0 1 4 5 1 3 3 1 2 2 4 6 3 2 4 3 2 3 2 2 1 3 2 2 5 3 3 4 3 4 4 1 1 1 2 3 4 6 1 2 0 5 4 1 3 0 4 3 0 3 3 1 3 1 0 0 3 0 1 1 1 0 2 0 1 0 2 2 0 0 3 2 4 0 3 3 1 4 2 0 2 1 0 2 1 1 0 0 2 2 2 1 0 1 1 0 2 0 2 2 0 1 0 0 1 2 3 2 0 0 1 1 1 0 
];
B = [
0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 1031796 848004 183792
 856491 703976 152515
 868140 714821 153319
 1012916 833855 179061
 1164370 963960 200410
 742064 611181 130883
 1191885 984957 206928
 1562330 1312330 250000
 832778 688286 144492
 997168 827265 169903
 1418820 1190888 227932
 1144737 951263 193474
 1156099 970469 185630
 960759 797815 162944
 1086077 905149 180928
 1179848 993261 186587
 965745 806389 159356
 1354662 1140234 214428
 1094598 914070 180528
 1129575 955202 174373
 1004816 842323 162493
 1305063 1102545 202518
 919074 772297 146777
 1350084 1142706 207378
 898727 755533 143194
 1219980 1036940 183040
 1289163 1092191 196972
 863139 725116 138023
 1260550 1067889 192661
 764048 640375 123673
 121641837 106640830 15001007
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 
];
D = [
13 54 0 0
0 5 0 0
4 14 0 0
8 12 0 0
9 5 0 0
11 13 0 0
64 38 1 0
131 37 7 4
750 59 11 6
1979 97 83 31
3208 130 380 141
6854 184 880 498
13134 369 1466 1164
25219 616 2660 2127
51528 1188 4454 3869
165382 2598 7517 7094
1032824 5172 12768 12113
5648944 10146 21363 21226
10883061 19027 37669 37613
4870117 30396 60414 60081
608932 44914 85338 85070
133603 64076 110557 110470
141203 91339 134031 134306
166080 124891 160354 160120
194834 164337 190043 189968
228347 205590 222403 222857
264767 247940 257536 258706
301877 287509 295506 295374
339552 325900 332769 333328
375257 365038 369416 369163
408543 397198 402728 402628
434532 425492 430313 430775
458949 452034 455080 454914
478126 473234 474535 475760
494337 490010 491028 492604
507865 504241 506310 506066
520810 518617 519170 519702
532214 532186 532922 533062
547636 545766 546999 545884
561769 559469 561417 560983
577855 577804 578030 577492
596271 595511 596480 595712
619345 617983 617177 617184
642236 642677 643667 643294
669791 671914 670255 670683
701008 699612 700238 700504
731384 730047 731078 731425
755189 756560 757165 757462
776108 777878 776988 777315
790385 789457 788782 789151
792267 789808 791625 790604
781729 779658 779030 782714
758451 760340 759148 759140
731031 730046 729681 730735
690867 690074 691704 690137
643439 643848 643063 642889
592744 592475 592788 592381
540982 540545 538823 540940
489391 489267 487836 490085
445989 445842 444787 445949
414282 412630 412523 413787
391124 391205 390148 390598
371292 372086 372804 369597
365922 365969 365396 366233
372948 372814 373078 373263
385922 385361 386597 386185
407365 406115 406342 407278
436560 435675 437008 437655
473863 473209 473760 473705
500251 500918 498636 501254
513431 513969 513078 513101
509573 511646 509513 509108
473769 475455 475696 475312
409234 409242 408993 408765
342460 342268 340892 342425
271019 269504 270037 270491
199663 199543 198805 199579
137502 136565 137104 137245
100813 100870 100367 100543
70091 69976 70081 70311
46524 46497 46439 46148
28926 29011 28938 29145
2778 2728 2698 2693
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

];x = [
10 12 15 19 23 28 35 43 53 66 81 100 123 152 187 231 285 351 433 534 658 811 1000 1233 1520 1874 2310 2848 3511 4329 5337 6579 8111 10000 12328 15199 18738 23101 28480 35112 43288 53367 65793 81113 100000 123285 151991 187382 231013 284804 351119 432876 533670 657933 811131 1000000 1232847 1519911 1873817 2310130 2848036 3511192 4328761 5336699 6579332 8111308 10000000 12328467 15199111 18738174 23101297 28480359 35111917 43287613 53366992 65793322 81113083 100000000 123284674 151991108 187381742 231012970 284803587 351119173 432876128 533669923 657933225 811130831 1000000000 1232846739 1519911083 1873817423 2310129700 2848035868 3511191734 4328761281 5336699231 6579332247 8111308308 10000000000 
];
