A = [
661489 813305 983883 582821 1085892 704060 703966 1024399 820731 980533 680738 726452 916609 745131 781871 676269 778290 763781 748275 738226 682410 796704 734537 709729 741169 676210 684084 690663 730451 723870 688490 723616 714533 638135 624458 684757 800456 679288 736019 796727 659654 643589 607291 663916 613772 629043 646687 614000 626609 579772 579224 615972 582642 607829 580482 554213 589957 533974 536214 526089 523037 547227 514011 528343 518452 496670 516283 488340 499289 483485 495978 492889 463743 474308 457305 471619 524307 516844 495026 498532 488757 463189 450031 441195 434193 435581 419586 393059 386022 380873 379960 379569 370028 366252 364461 357355 353121 347695 342272 333797 331786 330264 328415 327433 320093 319774 314484 309125 307196 301795 300665 295830 291704 289246 283614 284130 282608 280533 281277 276701 275517 271835 269222 266372 260560 260162 255256 253886 251233 246903 244118 240533 238655 236428 234136 233962 230083 226693 224388 222696 222079 217857 215649 212666 211509 208069 205143 203524 202131 199643 196392 194478 192349 189909 188339 186979 185690 182971 180129 178906 177660 175977 174475 170464 170873 168945 166736 164830 162470 161704 157958 158785 156818 156185 154942 151940 151917 148881 148904 147202 145966 144852 142342 140520 139984 137928 137811 134787 134291 134079 130785 130129 127717 127788 125926 124858 123705 121392 119992 118852 116865 116823 115394 117041 113739 112575 113405 110049 109324 107660 108054 108486 106511 104612 104738 101457 99848 99211 98334 97081 96347 95214 95112 96080 92524 90996 90685 89399 89965 87977 87553 86892 85889 85309 84633 84159 84020 82169 82138 81394 81382 80378 79379 78902 77668 77502 77447 76323 75847 75907 75176 74572 74072 73531 73223 72378 72282 71446 71990 70708 70563 71090 69594 69451 69530 69041 67689 66998 66692 66425 65658 65046 65285 63841 63597 63198 63256 62676 62659 61883 61332 60345 60772 59851 59512 59049 58915 58184 57999 58325 58408 56342 56091 56303 56026 55274 56137 54785 55081 53882 53388 54068 53051 53025 52453 53012 51617 50808 50620 50355 49766 50060 50801 49835 49051 48274 48438 47846 47806 47295 47059 47155 46389 47092 46009 46125 45580 45321 44893 44167 43872 44075 43979 43378 42853 42833 42165 41935 41856 41510 41413 40999 41162 40711 40544 40148 39922 39541 39302 38730 38799 38785 38842 38537 38370 37846 38015 37144 37360 37010 36726 36443 36528 36184 36327 35497 35793 35853 34915 35273 35137 35062 35127 33959 34169 35367 33439 33752 33282 34361 38665 34012 35665 35157 41639 41092 37923 34661 36366 33231 34397 33251 33324 33051 32064 31616 31516 30769 30249 29731 29700 29183 29089 28821 29062 28867 28629 28297 28032 28494 27821 27775 27261 27440 27333 27094 26965 26646 27608 26346 26671 26102 26401 25789 26086 26121 25857 25953 25495 26368 25723 25053 24985 24947 24870 25649 24555 26048 24041 24077 23966 23524 23768 24020 23386 23213 23162 23832 22754 23209 22768 22825 22377 22431 22265 22235 22286 22364 21901 22014 21455 21401 21726 21198 20920 21214 20823 21376 20783 20540 20900 21109 20342 20294 20522 20144 20289 20085 20295 19740 19535 19422 19672 19498 19094 19133 19277 18843 18791 18839 19034 18445 18302 19659 18281 18278 18147 17932 18209 18039 17638 17558 17426 17589 17450 17966 18287 17071 17119 17013 17051 17081 16679 16668 16906 16603 17363 16533 16559 16299 16487 15938 16382 15926 15756 15556 15651 16395 15538 15488 15191 15171 15190 14818 14769 14573 14789 14876 14389 14459 14301 14437 14043 14248 14047 14044 13989 14354 14134 14239 13556 13865 13484 13724 13901 14216 13376 14236 13308 13248 13183 12900 13077 12865 12733 13086 12909 12967 12632 12400 12649 12236 12248 12488 12127 12239 12141 12068 11679 12288 12279 11813 12041 11987 11640 11653 11656 11876 12268 11658 11460 12167 11959 12288 12045 12004 11896 11256 10684 10741 10825 11009 11592 11499 10659 10850 11821 10338 10409 13210 10398 10749 10175 10625 10487 10315 10096 10791 10197 9977 9891 9962 9701 10003 9846 9550 9460 9420 9568 9368 9502 9188 9199 9819 9212 9278 8966 8966 9130 9014 8802 8868 8803 8863 8642 8488 8517 9070 9399 8542 8303 8605 8296 8423 8607 8514 8656 8180 8229 8228 8175 7821 8091 7926 8083 7859 8045 7914 7779 7818 7955 7528 7805 7560 7470 7412 7470 7466 7329 7390 7320 7333 7114 7293 7076 7204 7245 7307 7069 7209 7154 6905 7320 7125 6999 7204 6886 6942 7011 7383 6704 6536 6596 6709 6979 6674 8568 6637 6341 6888 6533 6636 6533 6773 6371 6399 6327 6123 6726 6260 6807 6145 5987 6164 6264 6075 6642 5911 5949 5701 5954 5896 5755 5838 6051 5738 5667 5737 5746 5803 5560 5616 5704 5262 5290 5974 5609 5563 5343 5233 6044 5220 5324 5532 5223 5367 5339 5057 5173 5348 5165 5039 5022 5362 5650 4814 5006 5027 5048 4852 4705 4704 4830 4941 5021 4664 4485 4672 4850 4563 4692 4486 4518 5217 4533 4475 4404 4250 4317 4589 4500 4336 4375 4070 4601 4609 4365 4292 4128 4407 4291 4330 4373 4196 4225 4292 3987 4209 3939 3956 4167 3802 3919 3977 3953 3898 3866 4123 3906 4563 3922 3873 3986 3743 3911 3760 3717 3853 3757 3865 3778 3644 3664 3582 3923 3460 3520 3617 3476 3423 3424 3237 3420 3366 3419 3255 3211 3194 3316 3321 3271 3168 3198 3244 3149 3181 3060 3096 3171 3127 3061 3140 3144 2939 3040 3054 3128 2975 2862 2906 2868 2813 2943 2854 2904 2878 2834 2838 2749 2845 2797 2750 2623 2762 2706 2751 2788 2795 2756 2726 2562 2683 2619 2629 2609 2716 2580 2602 2572 2521 2535 2439 2441 2644 2533 2626 2521 2510 2602 2381 2516 2349 2321 2335 2262 2484 2444 2566 2271 2287 2265 2269 2309 2256 2196 2288 2140 2645 2194 2222 2064 2158 2373 2151 2161 2167 2048 2257 2254 2174 2106 2064 2092 2064 2088 2089 2142 1985 1991 2002 1981 1974 2133 1937 2040 1946 1899 1956 1914 1937 2174 1943 1853 1821 1948 1868 1803 1877 2067 1852 1856 1882 1823 1806 1800 1780 1904 1740 1717 1725 1743 1681 1808 1693 1876 2055 1709 1754 1620 1783 1824 1642 1619 1609 1716 1634 1649 1639 1699 1624 1607 1577 1635 1526 1528 1642 1532 1508 1564 1590 1411 1509 1500 1741 1424 1515 1362 1547 1484 1462 1491 1368 1530 1473 1425 1538 1352 1421 1445 1412 1437 1401 1411 1428 1366 1394 1326 1381 1329 1312 1325 1350 1387 1354 1909 1605 1777 1935 2129 3279 4916 4539 10370 12438 19940 20119 20017 18663 19351 18942 17757 16620 16844 20282 13176 9907 9925 9631 9134 9304 6333 4356 4805 2494 2745 2512 2359 2628 2457 2191 1666 1347 1324 1306 1346 1344 1283 1324 1348 1328 1241 1290 1213 1221 1278 1278 1231 1282 1162 1287 1222 1242 1273 1243 1256 1261 1239 1270 1180 1233 1279 1226 1201 1195 1489 1210 1142 1134 1210 1117 1097 1109 1150 1090 1121 1121 1001 1016 1018 1026 1110 1086 1030 1013 946 985 905 901 920 917 938 935 1063 904 917 1007 932 976 920 1068 942 1066 1017 1250 1760 2525 1454 1430 3894 3608 2350 2185 2915 1852 1841 2054 1265 1999 1474 936 950 897 1758 2069 1435 1545 1339 1112 1121 1230 1029 1142 853 951 3585 841 891 777 756 893 874 802 743 663 774 722 1055 706 681 657 663 670 790 648 695 647 624 651 677 580 680 628 680 609 716 679 676 630 797 674 592 580 590 629 858 598 607 629 533 576 713 595 606 534 693 700 675 617 567 558 593 526 905 771 1242 743 1162 770 671 620 954 704 680 652 539 610 549 584 763 594 603 530 640 569 550 562 538 560 558 499 459 539 504 506 508 518 484 475 482 474 489 524 473 831 669 664 622 534 622 549 594 585 622 519 550 573 547 576 563 492 513 530 675 499 465 568 484 545 537 966 1084 973 1103 970 762 688 935 691 990 633 733 562 589 706 1203 436 440 456 480 589 522 1055 502 890 1501 649 1010 1217 777 597 449 940 742 516 522 443 714 616 488 790 1010 446 791 464 667 1033 478 679 743 769 947 452 822 656 486 1077 630 956 595 481 598 756 432 1097 778 732 692 993 931 1031 839 915 685 677 701 865 789 1170 910 1071 1027 853 941 931 837 888 801 1121 870 757 825 557 645 560 664 563 416 417 371 346 358 347 318 295 303 327 331 305 1246 358 348 359 354 373 341 350 312 332 347 318 308 291 289 302 261 288 306 270 254 252 209 261 247 236 231 247 236 247 217 210 260 236 231 247 234 246 241 241 224 206 206 215 189 192 203 183 209 199 229 201 201 213 206 165 171 202 200 204 192 173 215 209 211 229 207 237 202 204 224 233 196 183 206 216 194 163 153 180 199 176 156 169 167 173 185 160 156 181 172 164 160 160 162 160 154 144 148 161 165 155 166 132 167 148 140 142 153 152 142 139 141 145 149 141 154 142 185 141 158 148 130 148 170 142 143 137 147 131 132 147 111 130 129 125 162 144 126 145 116 149 139 116 108 142 150 118 139 113 112 129 133 138 112 120 126 108 105 131 103 115 108 116 126 117 112 119 108 101 109 111 127 111 98 115 114 134 107 144 103 128 108 110 112 103 130 117 95 109 113 98 106 102 92 100 115 109 95 90 106 93 102 110 83 87 92 89 75 77 88 96 84 93 100 98 104 79 84 82 81 83 73 102 89 100 74 91 101 78 101 86 82 88 100 110 83 76 107 77 73 72 78 59 67 83 82 79 73 69 77 61 86 78 79 71 61 67 88 80 89 79 75 70 63 85 63 69 72 66 77 66 68 67 66 72 57 67 61 63 51 61 67 52 67 59 61 66 69 64 63 62 60 74 61 55 68 65 58 61 73 51 69 72 49 67 54 51 54 70 50 50 47 73 49 62 50 56 46 51 71 53 56 48 53 56 61 54 56 44 53 59 49 38 44 61 59 58 43 56 58 48 41 46 60 54 45 73 42 50 53 37 28 54 44 58 37 62 39 39 53 46 58 51 36 49 38 40 54 45 46 42 59 39 35 46 47 47 43 36 45 46 24 34 41 41 38 47 45 38 40 41 31 43 47 36 28 41 34 33 35 43 25 30 30 35 32 37 42 41 37 41 35 37 24 28 28 23 38 39 49 37 34 25 42 27 45 36 37 33 40 25 40 20 36 43 26 25 27 30 38 27 34 22 37 17 40 33 37 32 30 34 32 28 37 27 30 37 25 34 31 27 26 29 46 29 31 33 28 30 33 30 35 33 38 29 26 26 20 37 20 38 35 29 29 25 29 36 25 34 32 30 26 30 21 21 12 34 22 35 15 28 34 32 23 25 38 21 27 26 18 28 25 31 27 12 19 23 18 33 26 28 24 20 17 24 28 20 25 29 29 25 20 18 25 16 28 26 20 28 24 22 23 29 17 20 24 14 28 15 29 18 27 19 27 17 21 17 15 18 20 20 19 22 25 25 20 22 20 20 23 15 20 29 22 24 14 16 14 16 14 22 
];
B = [
0 0 0
 269424 131703 137721
 310094 181667 128427
 268573 163881 104692
 241034 150812 90222
 225035 139071 85964
 201483 125574 75909
 176752 105551 71201
 144568 96382 48186
 142376 89362 53014
 212464 154939 57525
 173099 125762 47337
 181078 137486 43592
 180028 140685 39343
 182170 144574 37596
 207262 171480 35782
 203103 169474 33629
 207324 175274 32050
 198884 170750 28134
 214686 186634 28052
 217175 191123 26052
 214895 190260 24635
 219408 191309 28099
 230715 202457 28258
 232254 199648 32606
 251853 222555 29298
 241654 212361 29293
 265309 235850 29459
 234841 212779 22062
 255458 229529 25929
 263769 236439 27330
 279043 250940 28103
 278594 252056 26538
 268110 244354 23756
 351296 317044 34252
 274048 251611 22437
 284486 259309 25177
 711124 634204 76920
 278987 257784 21203
 340626 311965 28661
 588867 529917 58950
 334741 307651 27090
 527833 478531 49302
 277580 257803 19777
 334036 308200 25836
 533506 483828 49678
 326308 302049 24259
 509579 464511 45068
 322152 298847 23305
 475500 435438 40062
 318458 294816 23642
 463452 424595 38857
 329584 305866 23718
 457597 421126 36471
 319322 297101 22221
 482877 443053 39824
 437432 403591 33841
 301527 281903 19624
 426601 394411 32190
 251673 237562 14111
 32311917 30849431 1462486
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
36 7 1 3
0 3 0 0
2 22 1 0
3 41 2 2
3 27 6 3
2 87 6 3
36 88 23 41
1281 174 54 48
131281 267 79 77
784807 426 134 166
1590630 701 215 232
2598491 916 451 492
3282316 1436 922 999
3850268 2279 2420 2394
4481049 4192 5640 5623
4159489 12754 13231 13475
3111733 19278 26470 26360
2047719 26275 37414 37587
1208371 40110 48442 49146
228298 55774 66783 67224
112035 73892 83659 83908
113714 85919 99605 99854
122068 106311 115566 116461
132949 121311 129943 130143
141388 135780 140090 140733
147374 145570 146456 146689
150465 151415 149286 149395
148646 149807 147675 148909
144576 146003 142835 144025
136616 137869 134025 135790
127253 126222 125237 126013
116232 115951 115138 115304
106676 106647 105600 106284
99702 99638 98733 99842
94977 94165 93985 94499
91999 90809 91255 91578
90740 89766 89601 89897
90492 90128 89733 90113
91595 90319 91295 91119
92286 92422 91986 92380
95196 94711 94134 94580
98048 97879 96992 98016
100819 100886 99566 100565
103397 102709 102990 102578
105299 103891 103521 104601
105764 105286 105103 105334
105378 105082 104638 105725
104512 103859 104200 105132
102258 101539 101558 102827
98237 98682 98577 99155
93696 93195 93662 94013
87808 88366 88633 88605
81849 81493 81477 81938
74893 74620 75382 75172
67618 67869 68153 67757
60401 60704 60618 60926
53967 54450 54211 54341
47948 48244 47689 48261
43079 43281 43093 43350
38557 38436 38619 38641
35364 35245 35557 35299
33020 32875 32907 33057
31022 30913 30936 30953
29856 29606 29532 29461
28574 28720 28759 28555
28499 28249 28773 28198
28572 28159 28407 28674
29063 28874 29008 28874
30258 29723 30506 29880
31033 31454 31286 30984
32507 32429 32767 32635
33780 33854 34514 33443
33775 33207 34299 33153
31754 30927 32026 30987
27830 27037 27984 27343
23742 22872 23802 23195
19398 18509 19056 18568
13919 13485 14356 13355
11767 10839 12106 10766
9087 7682 9413 7644
7178 4547 7192 4678
3558 2017 3428 1921
120 94 110 82
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
