A = [
5051660 4765515 19766634 4725422 4715795 4467348 4380679 4420101 4386940 4278872 4323743 4444543 4542225 4667052 4896880 5033129 5165967 5366144 5371131 5347559 5392063 5327899 5281466 5292657 5428973 7758850 7813741 7970013 10253839 9659144 9897114 9918312 9342806 9522594 9580282 9539619 9373019 9311945 9251600 9129955 9069279 9040192 9014947 8980729 8959061 8905270 8787966 8704329 8591344 8465337 8384572 8329602 8279188 8224688 8164808 8134370 8022520 7939441 7855588 7771771 7685333 7609807 7535517 7471890 7408931 7344036 7273754 7204220 7136684 7051951 6970187 6893634 6817289 6750388 6680702 6612032 6547613 6466643 6386109 6315350 6248576 6159548 6096519 6028342 5956751 5896257 5831140 5762358 5687727 5618817 5549133 5481974 5410847 5349274 5299620 5241232 5175797 5108443 5049400 4989083 4916604 4860341 4795963 4747659 4684905 4633129 4585338 4526340 4464916 4409736 4350416 4284407 4235614 4177792 4124023 4078694 4029624 3975991 3952435 3878293 3823166 3772524 3717152 3685088 3606377 3561758 3516581 3468579 3424950 3382566 3349305 3299285 3249701 3205572 3163062 3114272 3151623 3030757 2992920 2951110 2907290 2863480 2830931 2794680 2754525 2716277 2679330 2641126 2597674 2565038 2532760 2496073 2456208 2433822 2385713 2353099 2323463 2286632 2249061 2220113 2191198 2160169 2122567 2096861 2065940 2029417 2004097 1971255 1940404 1916787 1885231 1859031 1833299 1809380 1780010 1751604 1722978 1700792 1675070 1648951 1626398 1598248 1579872 1557962 1538381 1514443 1488309 1464856 1443656 1418902 1402697 1385103 1364392 1345904 1325317 1304549 1287564 1269349 1252476 1234069 1215009 1194694 1171387 1154403 1137804 1120601 1104184 1084901 1071786 1057581 1041614 1018912 1006014 984975 975009 961613 945791 930430 916131 905876 890691 875289 863563 848283 835302 821213 811801 801671 790361 774384 764967 753042 742493 729632 716051 707474 694427 684730 673609 662055 653558 643883 635009 626311 618756 608730 602641 590893 583375 574003 564906 557136 549241 540732 532525 523185 512277 508293 498914 491895 486397 475585 469660 466059 456142 449240 440635 433568 429640 424501 420162 411891 407004 402141 396155 387194 382864 377573 369848 369901 366737 356501 354068 346957 343973 337866 329300 326836 328273 320722 315696 310165 306311 302424 296533 292397 287168 283172 279988 281183 274141 267240 264543 263390 259595 251846 249201 249840 243804 239094 236301 234074 230845 228334 224183 220970 217702 212374 209126 204658 212416 197421 194696 190590 188190 190072 184805 178965 173935 172094 168684 166903 164121 162771 161170 156975 155537 153151 151887 150024 151411 149629 148033 147294 145288 143081 139165 136433 136103 133877 131338 132307 130292 125748 124254 123150 129671 119339 122678 117458 119044 115803 113830 111483 108021 107755 106740 105990 102241 101842 102921 98943 97947 98335 96925 95818 95328 93995 92908 91192 89427 88157 86970 85683 92793 89545 87739 87527 87439 87533 87159 85389 87079 83921 83251 80647 69831 69947 69502 68307 67663 67257 65593 65295 64614 65465 62993 62720 62357 61775 60687 59690 59387 59284 58913 57668 57014 56878 55961 54833 55287 53884 53236 52999 51946 51396 51385 50800 51055 49908 48667 47737 48092 47438 46592 46496 46065 45659 44587 44226 41949 42226 41766 41256 40584 40237 40073 39815 39539 38973 38694 38881 38089 37788 37373 37417 36391 36122 36130 35737 35621 34823 34629 34168 34148 33533 33532 33391 32760 32809 32251 31699 32134 31695 30782 30833 30219 30081 30317 30049 29696 29353 29145 29330 29054 28778 28316 28510 27920 28051 27560 27808 27808 27309 27276 26624 26855 27132 26272 26150 26116 26015 25494 26091 25348 25459 25253 25286 24683 24490 24507 24874 24319 24999 24760 24264 23554 23483 23332 23313 23163 23334 22621 22801 22888 23173 22391 22324 22386 22074 22015 21764 21682 21511 21619 21218 20969 20789 20647 20941 20254 19903 20118 20752 20446 19963 19817 20318 20138 20190 19930 19930 19635 19670 19704 19223 19469 19476 19594 18754 17866 17955 17919 17825 17425 17360 17383 17572 17686 17404 17753 17386 16933 16713 16942 16109 16126 15839 15900 15989 16278 16067 15583 15505 15240 15319 15016 15049 15065 14951 15409 15159 15144 15562 14779 14651 14762 14275 14626 14414 14311 14289 14279 13975 13946 13852 13869 13986 13751 13832 13744 13722 13790 13551 12985 13329 13263 13065 12999 13065 12721 12693 12570 12560 12445 12543 12385 12397 12299 11971 12266 12411 12455 11985 11819 11816 11824 12034 11549 11333 11620 11161 11464 11167 10953 11032 10634 10958 11110 10477 10567 10213 10266 10394 10582 10302 10715 10462 10290 10327 9863 9920 10086 10015 9912 10215 11397 10340 9948 9677 9229 9409 9258 9189 9287 8963 9175 9063 8931 9036 8893 9193 8772 8647 8595 8781 8489 8341 8388 8643 8433 8386 8684 8634 8602 8621 8530 8695 8681 8673 8595 8626 8428 8205 8658 8051 8351 8209 8149 8188 8410 8609 8203 8260 8433 8304 8476 8493 8609 8578 8519 8367 8289 8729 8963 8452 8276 8190 8547 8467 8610 8578 8307 9316 8424 8930 10182 9338 8639 8933 8468 8386 8384 8680 8041 7807 8731 8150 8137 7806 8286 7967 8102 7785 7853 8123 6895 7229 7223 7138 6679 6663 6447 6796 6306 6317 6216 6247 6021 6156 6424 6238 6169 6156 6162 6007 6263 5579 5469 5603 5623 5523 5428 5447 5588 5392 5639 5580 5346 5095 5230 5426 5303 5504 5462 5326 5295 5335 5306 5250 5188 5158 5120 4909 4827 4721 4709 4967 4934 4807 4840 4946 4871 4860 4955 4799 5043 4968 5014 4805 5060 4734 5013 4665 4663 4541 4602 4436 4508 4803 4611 4775 4728 4879 4711 5412 4829 5183 5192 4931 4909 4794 5010 5192 4933 5093 4990 4719 4542 4781 4866 5033 5024 4492 4556 4830 4402 4337 4016 4124 4166 3933 3882 3904 3822 3869 3854 3780 3870 4245 3848 3797 3903 4018 4040 3859 4020 3866 4399 4332 4427 4545 4443 4335 4383 4192 4061 3898 3965 3997 3501 3549 3494 3377 3578 3532 3959 3495 3550 3385 3398 3502 3397 3498 3463 3494 3701 3415 3522 3371 3349 3336 3363 3262 3153 3144 3247 3295 3332 3383 3164 3096 2922 3013 2922 2813 2821 2824 2627 2751 2687 2548 2589 2828 2681 2512 2529 2530 2453 2561 2365 2522 2484 2487 2540 2362 2418 2312 2455 2342 2348 2196 2307 2257 2301 2186 2304 2285 2231 2379 2414 2336 2320 2508 2455 2370 2436 2556 2383 2392 2222 2292 2194 2333 2077 2091 2030 2001 2120 2084 2126 2136 1982 2133 2002 2016 1959 2024 1944 1894 1906 1783 1881 1796 1806 1840 1920 1938 1901 1915 1901 1955 2189 1926 1887 1776 1753 1785 1801 1815 1722 1755 1808 1783 1733 1770 1801 1694 1714 1938 1866 1862 1838 1781 1695 1908 1789 1718 2052 1977 2052 2140 2083 1760 1979 1915 1810 1801 1893 1771 1989 1816 1984 1758 1758 1778 1907 1909 1991 1952 1586 1562 1554 1500 1608 1653 1797 1728 1690 1793 1656 1730 1719 1518 1517 1615 1578 1576 1553 1585 1536 1438 1547 1426 1469 1330 1347 1345 1329 1386 1513 1530 1563 1346 1260 1348 1300 1387 1352 1251 1334 1453 1388 1448 1380 1405 1355 1424 1372 1366 1411 1435 1457 1476 1481 1431 1416 1374 1355 1292 1388 1324 1235 1236 1291 1314 1319 1288 1228 1332 1261 1239 1219 1229 1221 1150 1144 1260 1299 1223 1311 1243 1321 1283 1274 1272 1260 1292 1307 1161 1184 1177 1166 1127 1157 1195 1174 1139 1113 1225 1142 1105 1240 1256 1255 1222 1237 1381 1366 1320 1277 1299 1281 1282 1370 1448 1469 1344 1340 1396 1419 1307 1353 1351 1378 1425 1532 1412 1671 1342 1414 1508 1456 1444 1347 1407 1745 1732 1739 1649 1350 1296 1426 1348 1287 1155 1170 1225 1251 1225 1206 1107 1268 1081 1156 1055 1074 996 1001 985 1000 1016 1045 1050 1047 1058 1021 1071 1028 1001 940 908 929 907 1001 828 917 921 973 996 999 920 933 975 738 770 772 739 771 771 800 773 796 777 706 799 772 744 719 748 735 778 744 910 712 679 721 738 750 741 731 747 762 761 736 758 758 815 779 751 759 727 789 669 765 767 749 759 771 745 746 736 778 745 735 713 655 731 713 926 923 872 945 888 845 928 939 882 889 891 881 1011 895 852 957 810 803 892 904 871 870 845 839 785 716 836 764 676 805 775 761 767 806 656 587 586 572 569 631 608 571 612 602 608 551 601 612 650 609 598 599 649 576 574 603 601 655 633 557 636 629 569 686 643 681 577 588 588 603 614 617 590 501 528 464 497 466 483 441 460 456 493 494 492 511 546 498 573 531 488 502 495 486 460 488 508 497 494 535 489 468 551 636 566 551 491 516 537 506 467 546 531 541 535 512 557 567 602 577 508 546 547 562 593 566 563 501 487 513 544 538 545 528 468 495 473 538 513 471 534 500 500 491 547 499 497 461 513 477 494 468 491 473 534 461 448 486 464 445 450 417 397 455 400 441 419 405 439 433 419 448 448 478 430 436 461 387 437 461 464 484 434 438 406 422 396 427 425 407 398 443 427 438 417 423 444 407 453 464 410 460 440 395 439 407 434 442 444 444 458 489 405 473 422 459 431 447 423 420 442 430 465 464 452 434 477 409 407 424 433 423 453 451 437 423 409 376 487 486 487 432 461 450 444 439 380 407 380 439 424 381 434 411 398 397 429 436 397 363 435 398 385 386 400 417 505 446 514 496 474 474 454 466 481 504 445 485 414 468 434 440 465 458 447 448 491 426 407 455 462 407 420 407 381 396 423 401 458 385 411 429 436 431 482 439 422 433 458 432 450 392 406 398 385 478 451 430 428 429 406 396 395 388 420 444 412 402 362 389 400 403 379 377 434 384 403 449 442 443 376 392 439 405 442 426 466 446 455 517 511 579 597 501 569 491 521 603 463 525 539 554 509 583 576 585 505 481 518 511 503 550 494 492 476 614 474 486 477 499 478 539 515 536 480 462 433 1285 1164 1520 1968 1879 1422 1299 1129 1514 852 304 295 274 280 277 304 306 310 285 311 302 317 327 306 320 333 343 337 318 354 324 314 323 370 345 343 350 339 464 369 393 339 356 383 377 361 342 402 397 347 320 355 354 321 320 363 371 305 352 343 301 296 351 340 326 330 339 338 359 277 318 337 293 352 293 343 310 281 299 275 315 280 233 256 249 273 237 239 255 294 263 246 248 287 318 330 314 272 265 266 275 282 284 280 250 269 269 333 241 242 231 245 242 260 262 266 286 265 216 253 234 238 230 265 264 274 252 262 277 244 271 237 290 267 252 261 261 244 235 282 243 264 231 232 288 288 275 256 255 256 246 253 258 269 246 222 252 263 236 220 225 260 244 193 214 225 227 235 233 233 246 219 232 250 232 222 207 267 269 241 251 223 218 235 210 227 236 211 234 238 233 255 239 265 222 241 255 227 222 253 232 257 254 236 241 256 240 272 275 257 233 269 237 237 247 232 216 196 232 246 251 237 264 274 227 273 269 240 233 226 197 241 251 247 223 263 317 282 338 344 353 230 270 275 282 221 238 231 248 229 256 253 231 241 245 237 228 249 212 238 237 250 228 220 198 234 202 200 233 227 238 228 246 230 197 196 226 197 187 192 213 209 233 219 254 227 223 227 238 243 223 208 224 248 230 224 237 231 229 234 234 232 222 196 195 217 198 214 197 226 234 220 231 202 220 236 233 183 204 214 210 215 191 195 
];
B = [
0 0 0
 2000173 116197 1883976
 1664939 123917 1541022
 3148160 219579 2928581
 1521391 112722 1408669
 1715383 130622 1584761
 2075372 161289 1914083
 2373795 192263 2181532
 2324123 204249 2119874
 4308315 400730 3907585
 2545424 283960 2261464
 4719103 675573 4043530
 2363126 277751 2085375
 2274383 231163 2043220
 1435871 190586 1245285
 2516152 208002 2308150
 1159115 104419 1054696
 1276633 135111 1141522
 1112465 99924 1012541
 2047497 161862 1885635
 1277428 115742 1161686
 3045105 256728 2788377
 2193057 189642 2003415
 2248925 230157 2018768
 3350319 235117 3115202
 4864661 392449 4472212
 1701093 237052 1464041
 12603601 940285 11663316
 1174761 200867 973894
 2692326 435367 2256959
 1361530 223102 1138428
 1461828 209020 1252808
 1136101 209871 926230
 3182304 368988 2813316
 975988 188397 787591
 1439001 246162 1192839
 1154938 204129 950809
 1285615 197610 1088005
 1090963 228454 862509
 3659238 409829 3249409
 803088 180289 622799
 1202976 252415 950561
 888461 195438 693023
 1924288 332088 1592200
 1316278 290004 1026274
 712095 159440 552655
 998838 218208 780630
 1263006 267140 995866
 5592375 574524 5017851
 1322283 322568 999715
 853962 196131 657831
 889732 211900 677832
 1424111 328355 1095756
 1038826 202564 836262
 6490121 760780 5729341
 1392671 307620 1085051
 1257564 299524 958040
 1014597 245778 768819
 3618875 463260 3155615
 3338886 518382 2820504
 405270736 81660530 323610206
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
311 696 14 9
169 113 6 4
250 178 3 6
216 232 5 12
181 279 14 8
285 343 144 38
2803 559 442 93
19301 698 640 283
129688 966 1219 592
692800 1469 1984 1299
2756948 2057 2790 2152
4608969 3721 4189 3402
6461307 6644 6177 5242
8783189 13675 8972 8404
10633371 26336 12656 11889
12215649 51055 17864 17475
12066271 87248 24072 23689
9953690 132335 31011 30830
6361173 179867 38772 38692
2630921 224859 46866 46814
615705 263233 54283 55394
143831 291428 62861 63598
106150 297057 72484 70992
105762 271734 79231 79394
106822 229737 86299 86856
110606 190292 92352 93834
115820 161192 100345 100444
117843 146061 107446 108054
125580 140105 116607 116660
130838 140945 126166 126396
139506 145347 135624 135956
151178 152989 145213 146169
166408 166572 155885 156041
179448 177536 168227 168804
190889 188685 180633 182530
201591 200326 194673 195234
215465 212637 207263 207768
227739 225937 221183 221723
235847 234745 230017 231767
239748 237759 235851 236242
240624 240944 237586 238006
234185 233743 232457 234745
222589 221554 220569 221191
202228 201233 201902 201377
176324 176690 176920 175466
146130 146333 146159 146097
111916 111856 111875 112055
79039 79325 79256 79235
51714 51632 51148 51798
28685 29146 28888 28807
13388 13212 12972 13165
4626 4599 4628 4578
1332 1293 1334 1234
166 230 219 201
8 10 4 12
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
