A = [
318700 314557 1769031 330683 327451 319619 320770 324935 329158 321296 339154 370073 413191 463211 525809 580769 609723 629708 635600 623725 604179 594953 590019 585883 590628 695089 696134 691973 777011 672568 676610 663168 563619 577899 562654 563977 556651 544286 540516 535438 541905 541894 543325 545646 542370 539773 536304 531767 526717 524812 524560 524086 526793 527843 526922 525395 523022 515947 514448 508808 509165 509047 509972 509280 510598 510312 507570 500872 500073 496100 492187 491338 492632 490740 488858 486602 484942 482095 477952 473665 470838 468020 467192 467931 466318 466514 464225 458555 454608 452085 449061 446546 443956 443705 442807 441731 440964 440233 439221 435858 435214 434622 432817 430816 430375 429847 427931 427067 423723 419924 416485 413660 412151 411079 408541 407310 406484 405191 402789 400155 396837 393379 391421 388794 387345 385794 384125 383155 380894 378045 375816 372102 370533 367876 364914 362312 362415 360640 358605 356767 354270 350708 347767 345509 343795 342203 339950 338456 338347 334628 333315 331173 328031 325800 324268 322096 320955 318419 317430 314385 312664 310540 308249 305769 304004 301439 300627 298323 297124 295164 294099 290363 288739 287298 284304 282687 279654 278118 276538 275113 271787 270806 269513 265933 264147 262588 260880 260507 257709 256469 254315 252970 251167 248096 245935 243715 241881 240810 237632 236048 234447 233702 230309 229895 227858 225692 224433 221740 220211 218671 216648 215358 213751 211434 210311 208091 205330 204273 202154 200664 198789 197488 196817 193851 192943 191335 188852 186764 184966 183732 181885 180425 178781 177658 175775 173806 172422 169983 168528 167113 165078 163139 162238 160880 158547 157351 154920 153807 151999 150606 148745 147311 145362 144026 142358 141005 139285 137418 136191 134958 133258 131755 130781 129228 128252 126161 124068 122975 121485 120874 119159 117491 116021 115019 112922 112490 110622 109458 108020 106387 105779 104729 102969 101777 100985 99458 98534 97181 95517 94486 92840 91784 90815 89726 88449 87053 86147 85479 83987 83150 82074 81063 79433 78958 77742 76397 75170 74361 73496 72689 71636 70526 69362 68694 67462 67026 65837 64485 63555 63477 62189 61339 60359 59869 58206 58499 56723 56504 55655 55220 54291 53798 52270 51290 50670 50231 48998 49261 48414 47825 46428 45798 45557 44906 44147 43482 42863 42172 41526 41001 40659 39744 38946 39058 38188 37713 37065 36722 35695 35605 35070 34381 34102 33518 33257 32511 32267 31900 31205 30947 30137 29665 29270 28508 28232 27712 27739 26896 26674 26241 25873 25491 25267 25183 24377 24054 23814 23459 23042 22874 22414 22380 22025 21477 21119 20990 20688 20288 19970 19741 19637 19137 18846 18502 18101 17766 17460 17495 17017 16753 16790 16573 16332 16231 15728 15411 14905 15022 14809 14438 14330 14363 14010 13576 13391 13473 13042 13028 12862 12560 12756 12251 12256 11752 11676 11606 11490 11383 11029 11029 10803 10779 10528 10127 10382 10014 10123 9566 9564 9495 9518 9173 9058 9083 8896 8857 8673 8388 8583 8432 8214 8131 7955 7893 7830 7671 7557 7463 7504 7285 7247 7228 6979 6939 6856 6915 6620 6687 6430 6454 6493 6325 6326 6103 6104 6085 5815 5828 5876 5757 5603 5549 5538 5316 5404 5439 5256 5330 5207 5102 5027 5005 4934 4939 4842 4887 4793 4587 4684 4731 4533 4442 4461 4516 4245 4263 4337 4231 4334 4223 4053 4088 3976 3998 3991 3959 3734 3895 3762 3776 3736 3634 3577 3505 3604 3517 3578 3502 3451 3430 3409 3430 3324 3279 3223 3232 3243 3182 3071 3137 3037 3135 3107 3097 3058 2980 2967 2889 2964 2845 2794 2863 2793 2854 2775 2819 2724 2634 2648 2701 2675 2614 2569 2588 2645 2560 2619 2615 2450 2442 2341 2418 2381 2453 2345 2419 2410 2343 2382 2362 2280 2365 2307 2340 2360 2330 2269 2314 2159 2183 2074 2136 2184 2048 2182 2188 2091 2034 2068 2042 1962 1988 2061 2055 1937 2027 1900 1953 1932 1921 1929 1925 1933 1793 1802 1749 1874 1754 1872 1813 1821 1776 1856 1733 1749 1763 1780 1724 1793 1765 1777 1647 1699 1776 1664 1649 1636 1714 1756 1729 1632 1682 1628 1716 1602 1565 1527 1587 1543 1601 1545 1587 1558 1562 1495 1529 1482 1499 1462 1517 1426 1439 1398 1409 1489 1446 1387 1430 1476 1432 1381 1382 1340 1347 1309 1397 1386 1390 1390 1324 1230 1358 1319 1322 1247 1281 1187 1253 1281 1212 1258 1249 1199 1199 1226 1227 1207 1227 1168 1199 1149 1165 1161 1202 1159 1194 1163 1185 1150 1143 1102 1106 1152 1115 1151 1119 1136 1050 1147 1008 1084 1064 1053 1059 1032 1028 1003 991 1030 1053 1015 1000 1041 931 963 963 1057 980 978 968 963 991 939 927 993 935 968 898 953 952 922 902 953 899 903 921 968 876 893 890 884 879 908 903 871 869 881 908 862 849 805 833 827 883 833 851 871 839 805 832 853 796 851 763 784 804 805 817 834 803 841 818 860 864 817 817 849 823 837 954 969 1063 1054 856 997 896 881 740 749 698 664 697 700 726 697 687 704 671 679 691 643 703 702 677 713 674 674 650 634 660 674 643 663 653 613 603 634 628 627 646 612 608 600 617 626 603 597 627 582 634 572 572 590 613 581 623 620 588 584 592 607 545 518 566 578 585 566 599 598 695 708 743 721 766 766 760 697 545 560 580 612 553 610 623 542 597 545 559 477 564 559 514 538 527 555 542 559 582 519 536 539 521 534 473 520 514 546 483 499 543 507 471 534 459 505 511 472 530 492 485 481 484 514 475 507 489 442 468 441 426 459 438 408 456 443 426 403 396 432 427 457 429 443 416 426 419 403 418 418 388 375 407 417 427 423 410 378 398 399 392 393 364 392 407 414 385 386 343 370 378 393 370 404 388 396 356 386 418 355 399 354 438 411 433 428 489 414 397 409 418 429 439 404 443 426 448 428 438 457 486 387 414 471 440 434 391 389 393 402 466 431 398 443 434 439 487 409 495 498 459 484 533 527 519 494 444 517 467 492 418 440 467 530 448 496 517 524 473 425 404 433 510 480 510 443 503 497 419 375 418 375 392 402 352 354 382 356 364 325 350 324 340 370 360 320 306 274 277 262 329 259 273 301 272 294 239 231 225 229 223 217 238 200 181 202 200 209 200 187 198 195 195 184 193 187 178 188 223 228 174 188 199 191 190 206 182 183 185 165 198 180 200 204 228 189 192 192 194 181 193 191 191 189 178 177 177 205 182 182 175 180 195 161 197 144 154 150 172 127 168 180 161 160 174 157 168 171 147 135 171 161 153 156 144 148 141 153 162 156 156 151 143 134 151 131 137 146 138 132 131 126 131 145 150 135 141 115 145 156 129 139 138 122 143 114 122 132 109 132 130 120 149 115 141 124 121 118 137 108 119 110 128 112 112 123 114 104 132 118 111 127 121 111 110 129 113 105 98 106 96 114 110 124 115 108 110 109 105 109 116 110 109 112 113 105 100 99 97 117 118 96 114 106 112 97 99 107 97 95 99 107 105 112 96 112 96 107 106 102 77 77 78 123 89 96 95 96 103 94 83 99 92 79 104 78 85 84 81 85 85 102 93 86 81 87 90 97 82 78 80 86 75 85 78 69 76 76 83 85 75 67 82 75 82 78 82 78 74 71 78 74 65 67 67 79 73 77 88 71 77 70 77 82 77 89 82 78 78 75 70 83 70 67 85 54 71 64 75 67 72 71 76 75 84 62 76 66 61 75 66 51 70 61 63 70 64 49 63 55 53 61 61 61 52 56 65 55 55 60 55 68 64 48 56 62 53 69 55 58 63 55 57 47 52 59 59 55 46 57 50 57 49 47 51 48 47 56 55 59 51 42 41 36 53 54 51 45 54 55 48 55 54 48 62 41 48 56 44 39 36 47 35 44 55 49 64 54 47 51 50 48 43 39 39 43 46 50 43 56 51 40 39 46 42 37 45 38 47 41 47 50 39 44 43 38 38 51 28 42 39 40 42 35 37 41 42 37 54 32 39 36 50 42 34 37 38 26 40 52 44 42 43 37 40 34 42 46 40 35 35 38 44 47 34 36 43 50 49 35 42 31 41 45 31 39 35 44 32 38 43 30 38 32 23 35 28 27 31 34 43 37 32 40 41 29 27 32 41 30 42 29 32 27 23 43 35 49 34 35 32 31 30 30 35 29 31 32 30 40 31 29 26 38 31 33 34 26 39 25 18 26 23 24 35 36 23 35 28 27 27 28 28 23 29 19 24 22 25 22 23 19 25 19 25 24 23 36 22 23 29 20 25 23 23 23 19 26 26 30 26 24 18 23 33 26 25 22 21 28 26 23 15 24 26 18 30 24 15 20 19 26 17 29 19 23 16 17 26 31 25 31 27 26 21 24 28 25 20 16 16 18 18 22 18 32 26 19 22 24 28 20 26 18 16 20 25 19 16 20 22 25 25 15 18 19 18 13 29 12 14 14 17 26 14 16 19 14 22 10 16 20 18 15 17 6 10 14 18 21 19 14 13 17 18 17 16 14 24 17 15 19 11 23 13 13 7 19 9 15 8 23 14 16 11 14 26 18 19 15 10 11 12 11 15 16 6 14 19 11 15 22 15 13 11 15 10 20 14 7 13 15 10 16 6 10 10 6 8 16 12 7 10 12 6 17 14 17 19 12 16 8 10 12 9 10 9 13 7 10 11 8 16 5 12 17 15 2 15 11 14 12 9 14 13 12 18 9 10 8 8 7 9 10 12 10 13 5 6 12 9 12 11 8 7 9 7 6 4 13 12 10 7 11 8 8 11 12 15 9 12 6 9 11 6 15 11 8 8 4 7 9 10 10 5 6 10 9 7 11 16 12 4 6 9 9 10 9 3 16 7 3 13 2 8 8 8 7 9 5 5 10 9 8 10 11 10 6 10 6 12 8 8 7 10 9 7 8 7 11 5 7 2 5 8 10 8 1 4 5 7 5 8 5 9 6 6 11 6 10 11 7 6 8 7 10 12 11 10 5 5 4 12 4 13 6 7 9 10 4 3 10 12 9 9 8 6 7 9 6 4 5 2 7 9 10 9 9 7 4 3 5 6 5 4 6 4 5 4 7 9 7 4 5 9 7 6 7 7 5 5 7 3 4 3 6 7 7 7 5 5 8 6 8 9 8 5 9 1 3 7 10 6 8 11 4 4 5 7 4 5 
];
B = [
0 0 0
 354219 178374 175845
 271203 141449 129754
 430292 244388 185904
 325450 191824 133626
 212761 122655 90106
 386577 258655 127922
 176069 111356 64713
 168065 114475 53590
 140441 92404 48037
 181171 122972 58199
 232802 158788 74014
 156215 103483 52732
 136894 93874 43020
 175417 125581 49836
 143749 101309 42440
 193712 140824 52888
 220538 160696 59842
 382984 288731 94253
 188837 138076 50761
 218132 163940 54192
 162504 121963 40541
 252994 193398 59596
 230743 176880 53863
 155304 117764 37540
 229633 176648 52985
 168354 129030 39324
 316569 245876 70693
 189571 145969 43602
 249205 192826 56379
 185505 142683 42822
 253482 197272 56210
 256010 199497 56513
 205909 159736 46173
 279371 217788 61583
 210531 164062 46469
 312515 244722 67793
 425177 331076 94101
 273811 214556 59255
 271323 212695 58628
 452728 353517 99211
 325580 255874 69706
 382329 299237 83092
 288013 226754 61259
 276413 217563 58850
 476587 374685 101902
 286700 226536 60164
 457325 359760 97565
 308577 244032 64545
 463544 365828 97716
 363860 288055 75805
 425695 336492 89203
 394373 314235 80138
 440458 348769 91689
 393273 312798 80475
 459738 365466 94272
 524035 417370 106665
 314595 250735 63860
 522150 416228 105922
 339210 268839 70371
 36973348 29537494 7435854
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
1 31 3 2
0 4 1 1
0 8 1 1
5 12 2 4
0 1 1 0
7 21 5 2
21 40 9 2
82 32 48 7
829 40 120 48
4528 72 177 82
11680 89 253 166
26238 128 464 261
57244 202 883 629
134002 360 1404 1078
314001 529 2112 1752
806890 973 3324 2953
1778440 1675 5086 4942
2324718 3141 7870 7776
1664321 5157 12018 11924
690214 7837 16895 16995
167420 11767 22821 22729
56465 16614 29100 29089
46548 23534 36094 36613
49338 32635 44076 44122
56983 43536 52658 52943
66214 55941 62594 63020
77715 69476 73620 73924
88588 82873 85571 85174
100316 94875 96845 97282
112310 105915 107921 108219
121388 115950 117845 118574
130601 123824 125344 126625
138678 130481 132902 132932
141112 137727 139145 138680
143850 141515 142665 143259
147352 145157 146607 146607
150127 148122 148984 149715
152399 151486 151870 151927
155807 154948 155368 155237
160196 159449 159676 159368
164351 163730 164027 164432
170513 170538 170034 170232
177812 177708 177133 177829
185553 184969 184032 184760
194111 193367 194055 193855
202546 202418 202752 202638
211033 210746 211039 210180
216863 217038 217249 217446
222402 222566 222558 222636
223977 224277 223819 224250
224120 225090 224393 224259
220948 220242 220552 220678
214707 213483 214437 215080
205804 205665 205623 206014
194945 194209 193958 193727
180166 181531 180985 180825
167220 167408 168027 167488
153751 153556 154234 154535
140265 140654 140651 140471
128627 129170 129375 129961
119605 119817 119734 119314
112160 112369 112868 112785
107186 107392 107211 107149
103586 103372 102908 103121
104559 104153 104430 104283
108966 108885 109836 109986
117589 117263 117055 117590
126648 126636 127068 127429
142094 141547 141389 142192
158352 158951 158267 158547
181849 181826 181904 181805
193666 193230 193534 193513
205975 206276 207064 206432
213983 212878 213207 212739
210369 211180 209931 211136
191275 191510 190223 191054
160661 159744 159781 159619
112461 112023 112437 111835
58695 58482 58586 58565
21009 20852 20937 20687
3274 3297 3307 3220
25 13 17 25
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
