A = [
4625632 4610642 19414990 4576599 4570398 4321621 4243624 4288970 4254227 4153489 4192147 4318302 4412772 4543722 4773437 4911083 5041500 5240319 5250992 5229994 5273842 5203850 5158042 5172662 5311866 7606254 7661476 7809377 10054032 9452627 9689866 9709070 9139136 9318828 9372414 9333862 9169465 9115492 9059653 8939719 8881514 8845279 8831121 8792189 8780002 8722241 8618276 8527230 8425452 8309167 8230780 8177502 8135723 8076287 8023210 7962715 7882755 7793577 7721461 7633800 7547453 7488302 7415459 7361940 7302613 7229933 7163224 7090445 7027088 6943687 6863387 6787484 6710968 6643745 6582395 6509682 6446764 6379434 6299963 6222664 6149798 6075133 6012401 5940468 5867244 5807699 5749824 5678090 5611451 5536858 5465908 5399989 5333129 5273095 5215047 5155798 5089069 5031865 4978864 4916076 4851776 4787523 4723825 4672422 4617532 4566769 4516784 4468989 4401721 4349728 4285813 4224520 4178541 4120409 4068025 4020893 3975180 3920837 3871870 3819588 3769730 3718146 3659910 3608857 3554795 3510175 3468347 3424126 3378283 3334533 3288481 3249531 3206089 3162268 3113357 3064646 3029671 2988357 2947148 2907816 2865895 2826450 2794821 2758272 2721415 2683205 2644078 2605044 2566066 2530414 2501250 2462617 2425602 2402311 2355082 2326239 2297550 2262902 2224954 2193576 2169985 2135755 2095117 2067203 2037065 2003903 1978468 1951932 1922218 1895256 1865888 1839083 1815438 1789883 1761789 1734281 1705193 1685171 1658094 1633479 1610677 1582191 1563803 1538333 1521048 1498983 1473003 1451801 1427849 1405277 1387463 1369589 1347363 1329784 1312096 1291304 1276671 1257699 1237404 1217547 1199641 1181263 1161974 1146292 1127618 1111254 1096316 1077768 1062670 1047982 1031794 1016405 1001160 982830 969792 959156 943086 927709 911931 902845 888843 874222 862248 847631 833183 819371 808756 799095 784660 769751 761161 750179 738049 725649 712007 704549 693457 684231 670588 659322 650264 645763 634448 625657 617660 607882 601129 589735 581664 573196 563047 555570 548041 540156 531253 520581 511889 508783 498287 490909 484466 474704 469009 464779 455088 448891 440786 434185 428778 423691 418620 411119 406872 403399 395816 386806 382177 377030 369188 368427 365555 356654 353710 346363 343435 337979 330542 327002 329021 319515 315447 309305 305049 302455 296073 293303 287834 283513 280318 281925 273419 268846 265977 264378 260499 254539 251653 252781 245744 239966 235647 233673 232350 230062 226448 222094 219571 214740 208492 205525 212529 198260 195668 191385 189738 190540 186545 178117 176208 172577 171532 169933 165885 164535 162288 158879 158202 155506 154062 151905 153399 152322 150138 149183 146946 144922 142080 138763 138719 135561 133659 134814 132301 127838 126470 126003 131756 121230 125089 119066 120095 116664 115470 113827 110406 109622 108531 108032 104740 103864 104980 100945 99918 99983 97462 97417 97282 95816 95270 93970 91511 90700 89469 88482 95928 92393 90254 89770 88965 89013 89410 87502 90084 86768 85897 83161 72812 72286 72026 71295 70672 69595 68239 68150 67069 68100 66623 65577 64335 63934 62696 62449 62181 61904 61578 60231 60064 59112 57721 56890 58115 56744 55521 54944 54244 53959 53433 52972 52718 51911 50824 50478 50524 49890 48864 48330 47804 47201 46407 45757 44245 44116 44225 43337 43388 42600 42796 42346 42005 41407 41223 41495 40884 40141 39959 39768 39120 39102 38345 38143 37280 36828 36487 36133 35934 35388 35417 35338 34656 34799 34314 33460 34013 33406 33084 33031 32311 32326 32635 31387 31600 31250 31091 31086 31238 30669 30473 30101 29771 30268 30322 29391 29125 28926 29616 29221 28735 28875 27742 27600 27698 27252 27452 27716 27323 27230 27152 27259 26840 27117 26258 26421 26160 26258 26391 26090 25716 25968 25055 24689 25143 25187 25008 24855 24594 24563 24705 24483 24520 23857 23812 24140 24222 23178 23042 22683 22936 22874 22923 22748 22278 21991 22255 22623 22604 22356 22198 22983 22890 22049 21830 21903 21352 21485 21682 21344 21119 21332 21831 21251 20848 21355 21298 21354 20842 22508 19970 20019 20187 19571 20512 20028 19974 19866 20306 19776 19478 19237 18866 18869 19452 19005 18494 18725 18512 18479 18155 18260 17985 17478 18085 18053 18231 18324 17881 17565 17403 17330 17743 17592 16804 17212 16607 16682 16339 16370 16369 16739 16182 16207 16094 15900 16097 15533 15200 15431 15360 15281 15049 14931 14604 14860 14267 14331 14534 14374 14221 14515 13900 13970 13738 14080 14331 13537 13501 14045 13557 14008 13234 13356 13556 12956 13133 12798 12638 12912 12680 12633 12473 12179 11943 12121 11675 12034 11939 12222 11886 11795 11509 11679 11600 11564 11449 11273 11455 11474 12100 11378 11379 10925 10666 10560 10471 10423 10472 10486 10489 10449 10127 10382 10020 10176 10220 9973 10253 9987 9899 9861 9915 9965 9874 9940 10012 10126 10110 10107 9988 9895 9969 9952 9892 9897 9603 9621 10281 9731 9948 9685 9652 9747 10090 10116 9843 9930 9880 9820 9924 10379 10518 10441 10300 9953 10176 10280 10404 10295 10056 9698 10355 10229 10431 10546 9997 10700 10119 10504 12209 11206 10655 11111 10022 10207 10269 10670 9550 9367 10351 9704 9494 9410 9879 9712 9532 9244 8766 9162 8769 9286 8627 8219 8166 7895 8029 8139 8041 7992 8102 7924 7824 8006 8263 8070 7989 8284 7964 8045 7825 7399 7323 7657 7595 7520 7520 7607 7538 7462 7457 7510 7260 7008 7158 7493 7034 7317 7464 7041 7301 7070 6912 6785 6958 6622 6707 6633 6954 6231 6140 6282 6529 6157 6278 6406 6286 6249 6252 6131 6183 6542 6390 6207 6249 6116 5976 5822 6013 6207 6331 6259 6191 6148 6151 6178 6323 5955 6302 6844 6151 6706 6672 6280 6531 6298 6161 6112 5919 5709 6057 5825 5596 5710 5650 5932 6049 5495 5441 5976 5527 5267 4868 4875 4973 4664 4666 4772 4867 4774 4790 4740 4878 4914 4893 4649 5091 5171 5182 5143 5164 5210 5341 5264 5327 5453 5110 5277 5007 4836 4822 4807 4981 4920 4430 4466 4652 4301 4263 4233 4710 4404 4345 4442 4108 4317 4275 4287 4170 4306 4403 4361 4163 4032 4043 4140 3934 3992 4217 4157 4135 4066 4199 4379 5594 4177 3969 4161 3902 3820 3986 3964 3778 3983 3871 3552 3623 3824 3848 3414 3495 3279 3440 3499 3617 3525 3499 3586 3388 3217 3327 3564 3323 3354 3276 3310 3360 3215 3376 3227 3284 3312 3192 3134 3429 3303 3356 3281 3172 2939 3165 3125 2914 2922 2869 2981 2879 2799 2710 2747 2713 2815 2960 2850 3023 2995 2759 2942 2879 2986 2686 2738 2734 2747 2749 2672 2679 2996 2673 2726 2932 2801 2775 2769 3003 2858 2754 2675 2653 2542 2582 2604 2649 2826 2618 2669 2520 2556 2525 2452 2359 2398 2434 2537 2542 2528 2520 2423 2481 2453 2484 2349 2626 2478 2577 2613 2646 2429 2517 2530 2338 2446 2461 2416 2617 2456 2648 2428 2380 2367 2582 2626 2685 2669 2278 2401 2282 2220 2317 2364 2354 2414 2467 2416 2257 2306 2240 2261 2157 2323 2306 2239 2203 2387 2243 2240 2252 2234 2112 2125 2153 2162 2096 2199 2096 2161 2177 2023 2146 2186 1977 2134 2106 1999 2189 2194 2137 2138 2118 2169 2124 2084 1989 1942 1981 1937 1968 1997 1957 1940 1996 1852 1894 1894 1915 1836 1803 1801 1878 1898 2002 1919 1836 1896 1817 1769 1775 1862 1932 1927 1789 1895 1827 1823 1838 1816 1957 1919 1856 1883 1949 1856 1898 1659 1747 1689 1791 1741 1680 1672 1733 1670 1664 1653 1525 1545 1737 1845 1778 1701 1721 1861 1834 1868 1773 1704 1732 1701 1832 1910 1854 1820 1846 1984 1928 1805 1778 1790 1818 1802 1911 1869 2171 1792 1810 1959 1879 1893 1805 1850 2217 2082 2142 2096 1732 1763 1775 1646 1680 1587 1497 1618 1572 1649 1561 1523 1625 1500 1446 1368 1338 1343 1380 1357 1315 1321 1372 1288 1232 1254 1217 1325 1265 1232 1242 1261 1248 1247 1245 1262 1323 1265 1308 1267 1347 1312 1321 1367 1135 1110 1099 1029 1064 1043 1040 1045 1078 1090 1041 1121 1055 1090 1108 1037 1039 1040 1056 1151 1060 1013 1124 1068 1008 1047 1056 1052 1104 1068 1131 1086 983 1050 1053 1075 1143 1147 1126 1086 1008 1113 1080 1104 1085 1138 1108 1030 979 1002 1019 1023 971 966 1027 1284 1261 1159 1218 1194 1068 1217 1231 1152 1180 1194 1112 1214 1112 1058 1254 1016 1047 1080 1110 1134 1064 1098 1098 1054 916 1059 967 937 990 1009 962 977 871 836 796 846 840 782 840 830 753 809 790 808 728 827 840 820 757 786 773 876 765 815 771 788 795 786 746 810 814 769 823 847 844 841 825 859 765 777 749 825 679 693 712 730 702 690 689 669 685 630 637 713 718 758 723 800 749 749 661 740 761 793 773 747 713 742 880 838 925 863 844 868 859 850 853 932 989 776 827 866 908 867 904 881 896 1031 1010 989 1210 1027 1024 1068 1151 1126 1276 1070 1210 1119 1054 1128 1121 1202 1026 1035 930 933 969 1076 981 985 927 1068 1053 1008 902 993 1017 705 721 729 658 727 706 677 716 666 668 633 670 647 654 664 656 657 654 701 676 592 620 614 667 658 635 616 622 602 599 613 584 596 597 576 563 577 545 575 507 523 551 499 498 502 549 529 516 546 517 492 549 508 492 510 536 556 548 559 572 535 531 520 521 560 535 570 538 514 512 679 543 503 531 529 517 507 524 446 540 510 511 520 540 472 501 478 477 503 463 465 476 483 490 409 449 501 506 493 489 492 460 509 494 463 446 485 493 457 448 463 479 484 509 512 485 567 509 543 530 499 544 537 555 542 589 544 595 518 580 553 547 535 498 492 499 570 491 521 483 534 466 480 437 450 437 445 484 480 438 457 479 468 499 522 527 488 503 524 476 531 483 509 512 501 541 517 504 516 499 507 507 520 496 470 529 531 583 497 504 495 508 487 445 500 427 487 499 477 541 486 478 528 496 561 559 571 528 552 605 581 677 706 679 621 566 560 615 584 609 589 571 583 626 619 651 595 559 584 582 595 642 543 577 549 650 579 574 578 594 582 575 570 590 641 618 557 626 1218 1546 2014 1992 1468 1436 1214 1611 945 351 411 383 374 366 419 395 388 381 415 385 381 395 382 373 369 403 431 416 404 398 400 417 471 422 463 449 440 573 464 509 443 497 513 509 437 436 453 429 427 413 428 408 395 376 415 412 387 402 386 351 370 380 405 335 381 392 359 419 347 363 298 336 440 423 404 330 323 332 305 293 327 310 345 304 318 309 280 312 311 320 307 288 327 300 330 286 310 314 281 284 288 316 298 316 301 316 300 251 258 294 265 254 270 275 293 301 310 263 264 283 260 281 288 289 297 283 288 274 246 281 301 345 314 300 259 311 260 311 300 280 239 272 289 308 318 301 300 298 294 295 267 289 300 287 239 281 297 289 288 285 265 305 261 296 280 280 287 288 292 299 280 277 319 264 286 241 337 297 302 313 275 272 283 286 297 351 280 272 273 284 296 291 276 276 291 310 264 289 323 267 276 310 264 274 275 284 284 307 268 273 300 258 291 269 269 261 271 240 271 293 287 323 334 293 281 323 284 286 266 302 261 331 273 272 258 291 268 281 273 277 306 288 290 272 262 255 277 307 269 268 300 271 259 274 239 251 246 239 255 241 250 248 272 235 239 235 242 264 224 239 207 261 250 257 252 242 234 225 255 238 251 251 239 288 262 279 245 267 300 254 252 251 269 246 248 262 261 253 279 234 277 230 233 241 255 224 240 214 258 249 261 251 239 263 273 264 231 230 216 241 260 253 235 
];
B = [
0 0 0
 3269337 703404 2565933
 2474621 547909 1926712
 4471982 1040004 3431978
 4376266 1000972 3375294
 2636114 598065 2038049
 8664970 2220796 6444174
 4686691 1136238 3550453
 2846895 715193 2131702
 5169143 1363802 3805341
 5017420 1233694 3783726
 1615660 402080 1213580
 11503875 2923638 8580237
 2047402 551817 1495585
 1464528 393248 1071280
 3148639 959448 2189191
 1560034 450672 1109362
 2396984 676948 1720036
 3998478 1207825 2790653
 1516044 420128 1095916
 1216015 351372 864643
 1187506 364357 823149
 1097685 346037 751648
 923985 293780 630205
 4881148 1647199 3233949
 1174950 379569 795381
 1958582 625865 1332717
 5354502 1835074 3519428
 1364429 458872 905557
 1910434 655294 1255140
 7572957 2516299 5056658
 1955320 694124 1261196
 2313979 839203 1474776
 5823315 2181781 3641534
 5083484 1899880 3183604
 7063382 2652984 4410398
 11345160 4271111 7074049
 13326900 4964686 8362214
 6826507 2554931 4271576
 13038210 5044981 7993229
 9283747 3495090 5788657
 2297100 896169 1400931
 14092253 5460253 8632000
 1963840 770794 1193046
 2344809 930255 1414554
 17246041 6788119 10457922
 2416695 962370 1454325
 7805701 2994658 4811043
 18729551 7720599 11008952
 7432733 2880073 4552660
 1943129 804249 1138880
 116732179 48365081 68367098
 1929569 817344 1112225
 3270959 1306015 1964944
 1794265 764637 1029628
 3491625 1420692 2070933
 3421705 1413744 2007961
 1880141 821391 1058750
 3371494 1397648 1973846
 1596334 715637 880697
 137559681 64023315 73536366
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
329 693 15 8
162 105 5 6
244 174 3 5
216 220 8 5
173 261 10 8
260 336 149 24
2670 546 410 87
18821 708 681 241
127966 945 1180 591
686900 1445 1967 1236
2742652 1969 2783 2068
4586629 3670 4164 3332
6428847 6544 6093 5177
8736019 13546 8942 8256
10574216 26062 12530 11751
12143277 50517 17595 17338
11993869 86383 23783 23472
9891975 131205 30588 30552
6320080 178446 38546 38155
2612152 222994 46517 46209
610890 260825 53868 54703
145686 289021 62639 62954
109546 294473 71588 70789
107173 269660 78981 78648
106165 228129 86305 85844
109908 189233 92886 92949
114774 160501 99915 100832
118217 145814 107959 107412
126819 141029 117064 116941
132350 142587 127273 127886
142519 148262 138477 138961
156038 157652 150021 150783
173719 173598 163148 163530
191258 189084 179934 180087
209082 207299 198573 199734
227208 226645 221554 220444
254121 251649 245107 246710
282155 281222 275500 276763
311463 310292 308056 308564
345810 345215 342816 342850
387619 389602 385181 385051
434427 434985 434761 434055
487450 487420 487172 485528
545552 545578 545823 547318
614645 615404 616192 614519
692584 694869 693211 696348
774069 779909 778353 777967
856503 858467 859910 858913
947889 949809 949508 948372
1040610 1041609 1040485 1038772
1125286 1123642 1125537 1123341
1198403 1200554 1198609 1199187
1265896 1267967 1264145 1263306
1327386 1326697 1327004 1325075
1389877 1387000 1389698 1390464
1429476 1428081 1427519 1428336
1488451 1486740 1483772 1484175
1527414 1530711 1528353 1524116
1556904 1556085 1559521 1554419
1583853 1586705 1586161 1584787
1609765 1613173 1604990 1607781
1566086 1558102 1558468 1561506
1443400 1446135 1445600 1445350
1209763 1210667 1212774 1215204
872924 875879 879159 872249
499354 498804 500997 496398
245523 252228 247803 248998
179568 178350 176755 176662
170256 169291 163472 170146
149001 154384 156609 146421
109737 112432 105511 116923
75503 70833 66994 78262
4578 5413 4926 4359
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
