A = [
1125336 1119052 7337772 993137 956622 895736 880962 865113 865108 867318 882381 911320 950685 995552 1049426 1107129 1166979 1230287 1296869 1360978 1421590 1485916 1540665 1595014 1644421 1871902 1918440 1952956 2160736 2017257 2083047 2107590 1953428 2000555 1988881 1988642 1972714 1926104 1906909 1871784 1847570 1826992 1793473 1775169 1754241 1731344 1716340 1698688 1684514 1672807 1654270 1637286 1628616 1614574 1604063 1592270 1580029 1572234 1559109 1547437 1540671 1528392 1529272 1520603 1510499 1510832 1504222 1600567 1603749 1597634 1696471 1693608 1690882 1677738 1663390 1650699 1637901 1624189 1609768 1597968 1581775 1569387 1555894 1541214 1528384 1515771 1501078 1486886 1474220 1459402 1446194 1430378 1416483 1401360 1391303 1376012 1361019 1345712 1328027 1315482 1301281 1287233 1269602 1256999 1240389 1230278 1215240 1200380 1184854 1174216 1159788 1146975 1132069 1119250 1106325 1093358 1082453 1068657 1055986 1045249 1033036 1021534 1009247 998116 984168 970594 961644 948851 936356 927747 914215 902961 892450 881561 870240 860154 849525 838477 828863 818910 807620 796511 786380 775782 766180 757640 746036 737253 727499 718141 709854 701503 692018 683239 674207 667515 658324 648675 640095 632416 623994 617303 607752 599886 592271 584815 575962 570311 562914 557174 547851 541755 534445 526927 520990 513945 506974 499833 495240 487360 480468 474845 468290 461552 455181 450305 444310 438207 433018 427488 421158 418055 409943 405241 398200 392718 387952 383053 378066 373108 368723 362841 358903 354519 348739 344044 340046 335253 330878 325050 322043 318311 313362 308831 304962 300954 297356 292320 289442 286177 281645 277099 273618 268198 265980 262387 258141 255640 251956 249359 245720 242150 238817 236748 233938 230735 227385 223690 220595 218432 214519 211863 209767 206273 203401 200566 198361 196288 192782 189894 187000 184653 182193 179981 177351 175442 172423 169716 168371 165391 162682 160444 159395 156814 154087 152638 150948 148659 146919 145608 143109 140875 138781 137543 135497 133405 132034 129853 127709 126527 124246 123563 121426 119926 118145 115486 114613 113763 112022 110696 108673 107662 105907 104754 103395 101220 100334 99093 97813 96478 94552 93994 92927 91684 90146 89308 87129 86731 84957 84386 83345 81780 81024 79783 78991 77910 76990 75919 74782 74347 72472 71676 70741 70615 68558 67982 67512 66033 64992 64374 63476 62211 61847 61036 60507 59521 58543 58283 57689 56684 55542 55139 54451 53923 52523 51989 51786 50844 50656 49622 48955 48266 47845 47609 46495 46224 45514 44538 44579 43720 42989 43108 42210 41344 40722 40376 39815 39503 39207 38341 38026 37620 36968 36807 35739 35395 35006 34610 34099 34066 33316 32987 32268 32111 31726 31661 31020 30363 30199 29837 29588 29035 28528 28652 28299 28176 27521 27052 26470 26331 26214 26086 25401 24993 24729 24533 24204 24052 23787 23061 23076 23100 22257 22107 22203 21607 21214 21145 20840 20814 20563 20425 20142 19932 19549 19486 19239 19084 18856 18811 18429 18065 17863 17497 17477 17485 17143 17063 16749 16801 16203 16185 16289 15938 15599 15707 15438 15336 15069 15095 14570 14597 14588 14259 14317 14042 13974 13827 13548 13320 13404 13169 13053 12783 12846 12634 12491 12561 12442 12007 12155 11943 11896 11662 11560 11768 11454 11110 11137 11019 11159 10865 10751 10775 10537 10454 10418 10183 10259 10053 10048 9948 9789 9737 9524 9598 9363 9332 9354 9351 9181 8916 8947 8835 8839 8611 8702 8533 8383 8479 8268 8190 8095 8157 7891 7927 7747 7728 7837 7700 7674 7610 7551 7397 7304 7276 7316 7067 7123 7087 7137 7018 6978 6957 6869 6817 6648 6763 6709 6437 6582 6543 6317 6286 6369 6242 6284 6167 6176 6097 6103 5985 6016 5974 5734 5896 5896 5816 5770 5733 5468 5611 5532 5532 5514 5292 5428 5304 5376 5259 5234 5174 5111 5066 5239 5105 5087 5104 4848 4860 4830 4853 4926 4656 4811 4760 4930 4690 4754 4760 4586 4601 4631 4646 4580 4527 4616 4528 4409 4410 4408 4320 4428 4364 4289 4246 4219 4173 4220 4126 4102 4059 4070 4029 3988 3994 4126 3872 3925 3836 3957 3898 3788 3889 3849 3800 3779 3688 3774 3718 3637 3693 3686 3509 3641 3580 3596 3616 3555 3456 3398 3408 3392 3302 3457 3395 3303 3328 3334 3342 3265 3347 3208 3171 3201 3233 3140 3151 3036 3129 3048 3094 3130 3065 3062 3117 2996 2992 2896 2982 2931 2888 2975 2902 2900 2832 2926 2812 2855 2888 2771 2794 2822 2809 2715 2695 2780 2673 2718 2632 2608 2645 2567 2624 2608 2585 2636 2603 2542 2531 2459 2491 2482 2378 2467 2509 2422 2403 2342 2379 2326 2361 2247 2360 2291 2354 2276 2282 2280 2330 2264 2290 2217 2234 2226 2238 2248 2197 2185 2274 2154 2155 2203 2102 2167 2116 2083 2074 2068 2104 2108 2116 2004 2135 2045 2106 2071 2008 1938 1977 1998 1969 1977 1965 1922 1905 1904 1889 1990 1885 1902 1960 1909 1852 1890 1936 1846 1931 1821 1803 1821 1800 1788 1839 1780 1814 1756 1810 1830 1839 1903 1803 1808 1832 1864 1850 1951 2071 1949 1995 1990 2105 2163 2182 2153 2105 2127 2076 2078 2062 1935 2012 1966 1813 1761 1784 1813 1810 1842 1722 1702 1786 1650 1580 1527 1555 1473 1513 1481 1493 1440 1517 1472 1405 1421 1374 1414 1425 1386 1432 1399 1385 1369 1384 1375 1322 1347 1284 1350 1360 1403 1303 1302 1356 1305 1299 1309 1295 1317 1288 1329 1233 1295 1235 1242 1232 1288 1220 1238 1234 1194 1194 1210 1308 1221 1144 1111 1201 1235 1189 1156 1206 1190 1146 1154 1163 1150 1196 1151 1201 1169 1192 1119 1182 1127 1178 1158 1140 1116 1253 1111 1200 1233 1202 1210 1143 1252 1185 1277 1344 1389 1222 1381 1341 1336 1283 1285 1290 1252 1388 1413 1377 1339 1278 1244 1292 970 981 1072 997 1013 1070 968 975 1068 1012 1032 1048 1082 973 949 978 989 978 928 974 1003 939 925 898 893 890 911 880 883 971 850 898 855 864 841 881 900 854 821 881 850 842 780 838 783 795 730 765 779 742 781 752 757 794 770 752 776 714 754 749 734 729 698 698 686 706 718 752 742 728 651 746 719 711 705 709 704 697 756 720 670 704 762 727 737 729 727 722 745 750 767 784 788 811 723 740 810 762 733 751 730 758 767 785 776 800 796 848 874 849 914 921 865 909 943 960 950 931 945 926 959 925 895 933 917 871 871 929 973 943 1051 935 925 890 979 956 851 934 893 881 830 832 842 712 736 701 717 693 701 718 675 691 693 657 622 599 593 629 611 571 530 516 503 545 509 511 497 444 451 421 458 434 412 415 420 431 442 457 449 447 419 436 414 402 398 409 372 396 398 363 401 358 374 395 393 383 374 383 386 399 367 352 336 391 377 361 383 381 356 389 360 370 345 354 372 323 373 337 366 344 337 357 329 354 339 337 355 342 331 371 316 343 326 319 315 317 295 322 321 299 316 335 330 306 337 324 331 309 320 302 364 302 313 303 308 296 285 326 294 298 315 312 289 292 309 327 288 275 313 289 315 296 277 296 283 276 308 254 280 257 285 275 270 279 244 281 268 264 239 283 260 241 275 253 226 282 246 291 235 247 256 221 256 247 236 251 240 236 221 228 257 225 248 216 245 214 216 246 231 266 257 231 216 226 224 234 231 238 233 220 212 225 222 188 203 208 200 205 203 217 209 216 212 198 182 186 184 214 203 197 194 208 178 195 201 218 165 197 201 173 185 196 209 193 197 190 187 188 181 190 192 207 194 172 188 198 186 170 143 179 208 179 168 158 162 163 169 182 174 176 156 165 183 175 157 154 166 172 161 163 179 166 181 151 164 161 157 188 155 149 186 175 144 157 152 168 146 164 164 155 145 145 151 169 149 150 168 183 142 146 144 137 132 146 142 175 123 125 141 129 121 149 137 137 138 122 128 120 132 141 131 119 111 128 123 139 129 134 139 129 113 110 106 118 126 123 114 118 125 116 118 140 132 133 123 130 106 113 115 127 120 132 111 134 135 119 128 108 106 103 121 112 102 123 110 101 100 131 122 106 119 96 139 91 116 98 112 114 97 104 111 94 90 99 103 92 97 93 115 92 106 90 113 99 98 112 121 99 98 92 86 112 78 93 85 91 88 82 85 87 92 92 103 95 94 106 93 93 95 91 109 96 85 101 82 90 102 72 63 72 87 91 73 89 84 89 103 87 78 96 62 88 87 100 75 89 75 84 76 87 83 87 86 84 88 73 94 57 89 82 73 77 86 95 66 73 82 94 71 71 73 87 84 89 79 64 79 66 65 87 86 92 63 71 80 81 95 78 66 66 65 66 80 61 84 66 71 68 57 77 59 58 61 64 61 50 68 55 46 77 68 77 61 67 60 51 69 59 58 56 58 62 61 44 61 62 57 59 56 62 53 58 57 41 49 58 68 55 52 68 46 55 44 62 38 47 45 46 59 63 59 35 41 38 53 47 52 65 61 50 42 53 44 48 56 62 45 56 40 49 47 59 53 43 52 51 43 47 50 56 50 57 46 37 51 42 35 42 59 53 51 42 42 45 52 51 45 49 36 63 46 40 43 47 35 39 40 38 32 33 44 43 46 36 38 39 44 50 42 51 36 45 44 29 45 45 45 46 40 33 40 41 42 42 34 39 30 42 38 29 45 47 30 46 37 30 39 40 42 32 34 50 40 36 41 29 37 35 30 32 33 39 26 40 33 28 35 35 39 31 28 28 32 37 38 29 25 32 28 30 21 25 33 18 37 21 26 29 28 36 24 29 22 20 31 31 33 18 28 32 35 31 19 34 27 22 18 20 30 17 27 16 25 24 30 30 23 20 27 26 25 27 28 22 33 18 19 17 22 25 30 25 23 19 27 27 14 24 18 33 23 12 21 17 25 22 20 21 17 29 15 23 13 12 19 15 25 24 14 11 19 13 12 25 24 23 20 20 16 23 18 23 22 21 12 15 12 17 22 25 21 20 18 20 22 13 16 18 19 17 24 21 19 14 14 21 13 15 15 18 11 20 27 16 22 15 8 23 21 17 15 11 16 12 21 16 21 21 15 16 17 20 13 22 6 16 16 16 20 22 14 17 21 9 15 9 19 11 17 13 18 20 11 15 15 7 15 17 8 16 11 18 19 10 14 18 14 11 9 11 16 14 17 13 22 18 7 14 11 19 8 14 17 13 13 13 7 10 16 6 15 14 15 11 15 10 13 9 18 14 13 13 13 16 12 16 18 15 11 9 13 7 11 12 7 13 12 13 11 14 7 10 11 8 8 20 11 11 8 6 11 10 9 12 9 9 7 7 8 13 10 9 12 11 15 12 12 16 9 17 7 13 11 6 12 11 16 13 17 10 8 13 11 10 
];
B = [
0 0 0
 713619 370744 342875
 796463 439008 357455
 641349 363603 277746
 1091030 684917 406113
 783356 501148 282208
 575831 383675 192156
 530648 358252 172396
 399210 271348 127862
 319892 220359 99533
 254534 176558 77976
 303014 210497 92517
 352168 245382 106786
 357712 250601 107111
 804818 573048 231770
 550967 399868 151099
 530150 388606 141544
 463714 345676 118038
 480045 362382 117663
 496755 376311 120444
 447206 339440 107766
 653123 493982 159141
 569803 434718 135085
 539080 411139 127941
 482726 370856 111870
 535782 411111 124671
 518254 399824 118430
 648904 499536 149368
 487516 378081 109435
 609947 472063 137884
 603223 467724 135499
 573826 446606 127220
 637007 495981 141026
 633626 493433 140193
 804265 627280 176985
 628724 492257 136467
 715076 559184 155892
 1485718 1164643 321075
 688267 539474 148793
 817175 642756 174419
 1342823 1055940 286883
 849503 668035 181468
 1278507 1005691 272816
 705626 556413 149213
 863858 681473 182385
 1323502 1043589 279913
 852191 673931 178260
 1292891 1021730 271161
 894176 706821 187355
 1287724 1018861 268863
 853553 677902 175651
 1273232 1009014 264218
 965392 765753 199639
 1280832 1016765 264067
 883644 703401 180243
 1378429 1095351 283078
 1281338 1018765 262573
 881193 702590 178603
 1295939 1032123 263816
 779216 622529 156687
 89984604 73558835 16425769
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
87 206 110 6
15 37 1 3
14 57 2 1
18 65 1 9
15 68 6 6
29 80 7 9
176 123 32 17
990 129 17 13
18198 167 44 28
175205 176 245 67
581022 242 1651 362
1405477 325 2489 1018
2659642 446 3233 1864
3945274 639 4830 3328
4464241 1132 7032 5694
4368435 2086 10287 9414
3613620 3627 14561 13906
2581486 5643 20214 19898
1561974 9337 27748 27745
714791 14370 37521 37094
236413 21509 47906 48022
86417 31345 59942 60190
76650 45300 74001 74239
89362 63181 89923 89890
107188 84737 108304 108700
128286 110367 131221 131348
153000 138876 156696 156574
180437 169335 184704 184887
210954 200242 214466 215287
241538 231323 245317 247226
270239 260249 275319 274135
298412 286897 299365 300819
322803 310621 321811 322867
336239 329934 341436 341297
347909 344445 354390 354731
358176 355200 365619 365295
367740 366536 373711 374758
376604 375419 382429 383409
385619 384698 392243 391850
396306 395251 402092 401493
408460 407880 413937 415227
422931 422783 427709 429420
441006 440679 444869 445407
458921 460194 463172 464574
478664 479954 484006 483282
499922 499499 503618 503142
519233 519921 522350 521387
533662 533719 536227 536915
544288 544577 545765 548431
548911 550935 549037 551814
547799 545605 547849 548921
538760 538971 537352 538381
520413 521641 522516 522911
496072 497382 495860 498312
466517 468777 467017 468344
435566 435173 433920 434034
400895 401308 399685 400705
367205 365625 364931 365544
334187 333644 333332 333547
303872 304144 303839 304600
279118 279776 277962 279004
261140 260603 260131 261537
247825 246809 246963 248496
236589 236731 236937 237683
237314 238458 238409 238529
248358 249741 249238 249534
267282 267186 266277 266713
288479 288135 287511 288545
321660 321926 321234 322198
359534 360430 359628 361303
410643 411738 411109 412100
439863 440509 437984 439849
466993 468049 466138 467906
482965 482054 482698 484612
478291 478140 477420 477486
431641 433537 432774 433102
362221 362232 362202 362726
252479 251722 251521 252895
131207 130060 130248 130979
47374 47170 47431 47311
7300 7384 7603 7372
51 49 38 51
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
