A = [
547569 566909 2120127 595544 583535 552194 547987 550852 557522 546085 569794 614537 660314 722273 811616 872238 933319 1019186 1038567 1042665 1072491 1061966 1055348 1066801 1088228 1277619 1261820 1242270 1400384 1227523 1239472 1213072 1019935 1031396 1031872 1021040 996135 983342 978806 961597 953681 949028 950540 945290 944509 940787 927511 922401 909372 894097 887897 886781 881887 876147 871737 865065 856136 849292 842356 836020 826082 821089 815208 809613 804798 794962 791592 785772 780876 771247 762598 754542 745908 739268 730218 726519 718278 710593 701996 697154 688204 678839 673601 664377 655722 650054 645426 635863 628855 621101 615160 607087 601318 592232 588650 581501 572482 566337 561353 554475 545231 538592 532455 528133 522406 517615 513809 508633 498275 493114 485880 480340 475233 468747 460991 457091 453333 446895 441002 437235 432058 426007 417010 412731 405365 401783 397695 393974 385395 380761 376053 372722 367617 361868 357208 351019 347127 341916 338470 332996 328362 324383 321323 319191 314451 309793 305550 300949 296221 293377 289296 285192 280642 278768 270949 268204 265802 260047 256669 252759 249172 246570 242340 238270 235340 231590 229411 226375 221604 220024 215843 213232 211324 206665 203199 199068 195457 193142 189203 187552 184093 180873 178743 174637 174459 170534 167941 167425 166022 162283 161042 157125 154033 151906 150502 147483 146947 145972 144419 139655 138207 133693 131432 129920 127051 125439 124410 120995 119715 118965 117298 114632 112192 109637 108663 107721 105389 104128 102139 101245 99813 97998 97693 94882 93181 90812 89222 89380 86534 84348 83481 82284 81825 79724 77966 77608 75458 75276 75174 72413 71506 71016 69591 68952 68928 67313 66685 65947 64403 63690 62225 61916 61450 59660 58548 57133 56106 55818 54007 53715 53354 52208 51622 51719 50857 49016 48581 48479 47566 47060 46965 46284 45868 45535 43998 43216 43106 41597 41323 41331 40419 39726 39258 38861 38930 38045 36477 36380 37054 35531 36442 35371 34375 34346 32990 33163 31953 31528 31570 31695 30314 29831 29518 29608 29322 28471 28224 28834 27334 26485 26104 26423 26571 26137 25776 25394 25382 23614 22471 22237 22687 21394 21163 20918 20944 20843 20671 19428 19445 19274 18997 19629 19450 19311 18694 18086 18548 18335 17926 18036 17867 17785 18211 17887 18399 18560 16783 16131 16193 16132 15932 16387 15804 14668 14423 14126 16522 14159 14511 13876 13930 13896 13648 15343 14447 13633 13922 13303 12896 12354 12852 12222 11978 12021 11760 12253 12166 11402 11364 11068 10854 10653 10472 10351 11461 10795 10271 10292 10677 10691 10752 10534 10979 10404 10381 10086 8544 8583 8643 8645 8318 8717 8237 8425 8430 8599 8147 8195 8467 8618 8365 8618 8394 8598 8479 8160 8228 8110 8184 7607 7374 7093 7065 6760 6802 6830 6582 6826 7284 7034 6557 6195 6256 6410 6093 5981 6293 6011 6108 5797 5306 5609 5418 5398 5191 5152 5155 5450 5108 5123 5295 5414 5552 5260 5367 5399 5392 5180 5059 4859 5247 4800 4776 5146 4926 4894 5280 4754 4716 4942 5187 4788 4755 4622 4483 4358 4141 4049 4264 4023 4204 4349 4186 4315 4289 4328 4191 4120 4108 4332 4406 4187 4164 4101 4526 4152 4141 4087 4090 4181 4215 4102 4200 4106 4102 4094 3912 3792 3883 3854 3709 3846 3875 3819 3975 4469 4430 4495 3846 4771 4762 4147 4271 4279 3958 4225 4357 4289 4247 3818 4099 4494 4050 3972 4149 4175 3996 3809 3847 4785 4074 3723 3806 4184 4086 5484 4858 6755 7889 5312 4258 3832 3926 3693 3589 3658 3289 3351 3411 3346 3308 3508 3422 3484 3376 3317 2940 3091 2940 2967 3201 3155 3140 3081 3155 3178 3090 3068 2870 2806 2876 2812 2944 3133 2903 2842 2894 2774 2695 2682 2845 2855 2937 3075 2828 2760 2803 2962 3004 2808 2729 2903 2702 2693 2658 2596 2720 2908 2638 2631 2677 2637 2694 2569 2451 3063 3168 2672 2496 2523 2319 2408 2447 2423 2728 2396 2161 2211 2099 2145 2203 2293 2300 2061 2120 2213 2186 2169 1919 1979 2100 1926 1989 2018 1907 1933 2076 2131 2162 1913 1840 1775 1634 1783 1796 1710 1719 1596 1646 1578 1574 1490 1572 1520 1498 1647 1737 1665 1660 1601 1503 1506 1531 1560 1568 1573 1643 1557 1493 1394 1577 1560 1689 1517 1808 1660 1593 1576 1556 1552 1554 1621 1601 1634 1607 1749 1766 1659 1523 1589 1642 1524 1620 1640 1596 1518 1576 1574 1653 1582 1980 1871 1940 1831 1848 1842 1867 2202 2260 1926 1916 1970 1747 1773 1864 2138 1896 1738 1811 1839 1759 1869 1734 2330 2144 2209 3272 2792 2509 2270 1864 1993 1849 2128 1753 1967 2221 1854 1919 1844 1930 1557 1851 1807 1649 1633 1515 1749 1390 1279 1378 1341 1345 1602 1643 1572 1699 1544 1494 1600 1616 1672 1643 1833 1721 1600 2227 2108 1766 1682 1458 1515 1490 1791 1609 1835 2188 2189 1703 1254 1471 1567 1728 1370 1560 1420 1587 1430 1391 1394 1408 1380 1278 1298 1417 1303 1339 1391 1902 1672 1314 1272 1267 1276 1244 1290 1421 1412 1316 1226 1182 1193 1057 1142 1052 1121 1115 1060 1175 1238 1075 1172 1102 1042 1220 1424 1325 1384 1350 1334 1417 1468 1315 1321 1436 1446 1226 1260 1119 1247 1251 1265 1501 1572 1058 1132 832 798 815 724 778 717 765 743 696 737 761 721 791 778 811 804 795 796 755 850 876 767 799 787 857 815 725 762 703 723 831 719 731 756 689 654 652 703 675 625 720 690 692 647 590 619 673 667 622 649 632 720 649 592 690 759 582 595 639 684 628 617 666 771 850 665 682 683 597 571 638 577 530 606 601 576 551 562 595 500 520 470 544 541 596 634 535 540 562 484 543 560 655 611 510 501 518 590 651 605 611 533 502 531 552 585 624 592 520 569 682 561 515 535 491 503 521 474 509 477 484 500 634 578 541 560 670 633 588 554 535 456 533 537 459 504 510 637 588 558 506 531 569 627 550 546 503 448 474 487 520 480 461 493 485 426 381 376 416 407 382 407 421 412 395 355 396 391 403 399 367 347 410 425 441 413 434 424 435 392 391 502 491 514 494 514 508 428 431 453 532 507 521 499 465 448 447 401 461 477 445 485 485 413 426 465 431 460 409 406 442 422 373 455 388 397 498 491 410 428 426 415 342 410 417 443 427 366 375 407 376 415 398 356 439 421 410 374 429 438 389 336 348 364 342 346 420 357 392 413 437 384 373 342 406 388 353 380 390 401 406 342 404 463 344 335 281 320 364 312 331 304 315 289 314 328 400 354 440 334 330 316 306 290 271 285 286 359 302 312 293 268 321 320 313 265 303 323 290 278 265 326 312 309 335 319 278 298 406 356 375 355 315 382 358 354 333 393 427 315 397 374 434 363 379 412 429 371 415 418 478 449 505 486 348 380 357 369 380 345 328 349 321 365 294 313 334 289 281 238 220 271 277 252 319 275 352 246 277 289 265 266 281 239 239 238 275 228 230 253 267 232 284 242 293 254 246 257 221 229 195 185 177 182 222 187 196 191 216 181 140 190 193 190 187 207 175 246 203 194 189 193 201 207 229 179 211 221 199 202 198 188 172 204 227 246 236 266 246 283 238 256 250 298 266 207 192 180 198 196 173 150 172 210 198 190 245 200 218 265 237 209 219 254 208 219 220 212 241 198 179 193 215 218 197 208 195 174 172 184 153 153 152 180 172 192 146 145 152 145 128 130 172 160 125 142 117 115 123 122 93 134 131 110 117 137 115 107 122 101 149 125 108 141 149 127 159 148 149 138 144 130 130 112 126 106 90 124 125 110 123 96 107 115 104 86 97 98 119 165 147 192 164 150 133 125 160 155 130 138 133 129 164 156 168 162 167 170 162 170 179 196 192 147 168 147 193 146 179 156 155 150 149 190 243 148 181 182 208 205 232 191 234 189 206 265 207 204 191 173 155 170 173 192 150 159 167 183 161 176 162 156 154 92 126 87 82 99 107 99 92 77 85 73 92 87 85 96 84 85 83 79 92 67 66 82 94 88 89 72 79 77 53 99 80 82 88 98 85 91 81 93 95 90 94 75 73 72 65 73 74 84 69 90 70 63 71 72 67 71 67 85 86 76 77 68 66 59 64 52 68 81 53 80 65 74 64 59 66 61 61 47 56 65 55 58 86 61 66 73 81 66 69 61 78 68 66 59 64 69 71 76 72 67 50 58 58 61 57 76 73 55 73 67 69 71 92 107 92 104 85 60 75 99 101 88 86 73 90 107 119 96 113 116 91 106 99 98 65 77 72 72 71 78 76 86 80 66 66 80 84 90 73 81 71 78 78 103 94 92 101 125 91 83 89 110 100 89 77 78 67 74 77 93 94 73 93 78 91 103 115 87 75 75 95 93 80 91 91 100 125 114 74 104 95 115 127 110 136 138 111 150 121 162 202 230 184 201 172 203 139 142 183 173 215 159 188 171 211 216 216 241 199 202 213 174 157 169 240 169 153 142 253 204 328 210 181 204 176 177 303 449 864 776 703 456 418 296 408 195 45 73 48 44 66 58 77 57 71 90 65 65 56 67 55 62 69 68 64 53 84 48 72 66 81 72 110 100 165 89 102 85 73 95 76 78 70 89 69 75 84 58 69 72 48 98 90 77 76 69 57 59 60 80 68 65 88 88 112 63 67 50 60 108 72 79 69 60 65 43 47 45 50 60 49 51 42 38 62 42 43 48 30 50 35 33 51 48 44 41 40 52 40 50 46 36 37 37 37 31 33 29 21 32 33 29 59 44 25 24 40 47 41 34 33 38 39 38 23 34 36 31 44 46 40 27 38 28 40 42 42 36 29 41 33 37 35 33 42 33 41 33 40 37 44 26 46 34 46 30 26 26 33 36 43 27 27 30 39 46 37 35 32 34 33 39 27 61 43 35 41 38 28 41 26 36 39 37 42 34 41 33 23 37 32 38 38 33 32 44 36 38 34 26 39 38 37 37 39 38 24 26 31 36 29 34 35 34 20 36 45 31 41 43 38 49 44 46 45 39 32 44 40 29 29 35 31 32 27 39 46 39 29 41 28 35 29 29 41 39 24 40 29 32 34 29 35 22 16 41 38 35 33 32 31 28 26 31 45 37 27 18 33 38 27 32 39 34 26 28 37 29 33 24 45 34 37 40 29 43 26 44 24 37 40 29 43 42 34 36 27 32 29 36 32 33 23 23 24 21 48 44 38 37 27 41 35 41 20 29 36 34 28 37 
];
B = [
0 0 0
 439946 187809 252137
 408748 189026 219722
 568649 243295 325354
 682179 293621 388558
 401766 174692 227074
 1435474 659887 775587
 715460 318500 396960
 485260 242285 242975
 664676 304518 360158
 460330 191879 268451
 195983 89198 106785
 883335 331641 551694
 200236 87962 112274
 207633 104414 103219
 310214 142147 168067
 178513 80880 97633
 368058 176232 191826
 419345 183567 235778
 235982 113420 122562
 187411 94136 93275
 200044 103205 96839
 192279 101553 90726
 148672 77793 70879
 448940 208239 240701
 157210 78401 78809
 283134 139527 143607
 486871 219713 267158
 178080 89151 88929
 236485 116356 120129
 602699 260184 342515
 244777 124261 120516
 254652 128714 125938
 477879 224322 253557
 425615 207118 218497
 501206 244223 256983
 821221 386968 434253
 1097296 500219 597077
 505261 243817 261444
 923078 436123 486955
 849577 383461 466116
 284621 148814 135807
 1193226 546803 646423
 258821 138051 120770
 298858 159753 139105
 1423236 653072 770164
 310897 164558 146339
 753288 349372 403916
 1484048 715785 768263
 770504 364523 405981
 274315 148505 125810
 8821948 4219567 4602381
 277354 154645 122709
 505515 250082 255433
 256714 142764 113950
 548992 276322 272670
 535575 271658 263917
 277990 158944 119046
 535462 271683 263779
 238316 141358 96958
 25615769 14665291 10950478
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
74 79 9 8
31 29 1 0
61 41 0 2
123 51 2 7
133 55 5 8
230 64 28 8
1104 112 93 22
4706 138 127 38
25966 247 195 96
179250 352 252 165
849580 442 346 226
1552127 733 517 358
2180576 1080 1154 554
2866419 1866 1777 823
3245817 3534 2526 1203
3293253 6824 3605 2180
2744001 11875 4861 3547
1790906 18115 6407 5401
833483 24442 8049 8415
253676 31430 7946 8182
58844 36467 11383 10536
23491 43482 14461 12385
19193 50226 14048 10383
17092 43318 18748 14576
16508 40771 17796 23832
17559 38915 12324 16197
25120 21119 10761 10861
17509 16830 10537 10380
14126 20027 11623 11177
12837 15388 14218 12357
13293 15092 12497 12982
18507 17602 13071 13343
15850 15689 13690 13980
24926 25211 15142 14964
18762 18207 16555 17317
19526 19271 18269 18337
21720 21499 20084 20256
24416 23610 22812 23111
25515 25716 25244 26154
28036 27998 27681 27242
31554 31747 31534 30673
35466 34973 34834 34980
38836 39304 40102 39335
43769 44509 43863 44213
49482 52388 49449 49744
57805 59681 58254 63384
64065 65593 68695 65090
71385 71952 69645 69750
77412 76696 78421 77298
86413 84093 84618 83902
92817 91678 93039 91780
97402 98677 98760 97721
108269 114137 104154 111403
110239 109001 111049 110552
123112 119403 130628 125926
121601 127830 125488 120650
125499 129137 136625 125698
140845 139058 138507 132957
141294 132997 136142 132150
144165 138773 138809 145126
160731 159532 149144 155983
148094 140062 142153 143417
140853 134497 136163 136217
126835 119167 112662 118700
89525 94989 99578 81811
57333 67296 51983 62672
55327 63185 42942 47200
51206 61985 58431 57845
49862 46292 46381 40486
30531 33021 47359 26324
23291 21564 22842 28586
26016 21804 18346 18689
915 1165 1508 752
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
