A = [
631468 1240911 1702865 782091 1428855 1051099 1021771 1062642 1070498 1038808 1034362 1055883 1019281 991325 1008711 995818 981561 997215 991994 981602 984979 958608 944117 926504 894419 914838 920525 899410 901829 920002 898097 880224 884309 853740 846930 852566 842974 833617 847559 840720 827583 826348 817540 794210 792546 785128 777304 779877 775351 766018 775011 758628 740741 736931 719765 710648 725019 706822 700089 706120 696057 681008 682968 668396 651959 652752 646303 639032 637174 629461 618514 620872 607708 595081 595962 585623 575539 578232 572755 561008 563943 551642 541648 542104 531676 520664 523174 511845 507516 506264 497832 492773 491831 480557 472996 473400 464760 456183 459508 452548 447507 443587 438192 430845 428479 421386 414597 414089 409111 404123 403655 396782 392017 389606 382940 378872 378158 370825 364177 366260 360705 354747 353367 347945 341767 342539 336972 331843 331245 327078 321221 320837 314857 311366 311411 305728 302552 301703 295875 292483 291699 287256 282470 283971 277962 274367 274394 269701 267154 265353 260106 258163 256219 252344 249874 248132 244559 241282 240008 236469 234254 233489 229512 226014 223805 222548 219856 218872 216642 214043 213236 209580 206026 204747 202120 199594 200165 196065 193922 193395 191057 188804 188572 184849 183083 182978 179708 177328 176836 173529 172241 172015 169399 167619 166088 163673 162000 161515 159757 157973 158119 156396 154086 154087 151892 149171 147933 147208 146316 144950 143809 141905 141826 140192 138590 138175 136746 135240 133695 133089 131047 131728 129505 128230 128202 126073 125468 124274 123145 122139 122047 119525 119232 118110 117384 116114 116244 114271 114837 113401 112576 111263 109781 110446 109120 108378 107605 106751 105500 105468 104044 104360 101883 101945 100476 101487 99641 99792 98082 97354 97777 95583 95504 94930 94257 94165 92887 91895 91088 91881 90827 89792 89273 88633 87554 87340 86862 85811 86091 84804 84162 83692 82806 82956 82713 82016 80757 80741 79900 79176 80249 78469 77792 77771 77212 76467 76367 75023 75228 74654 74518 73475 73806 73213 72070 72360 71539 71258 70798 70275 69111 69753 68682 68007 68217 67060 66654 67372 66147 66306 66133 65077 65171 64279 63814 63241 63586 63489 62604 62599 61540 62045 61772 60961 61309 60845 60474 60048 60026 58952 58833 58838 57504 57733 57318 56894 57190 57111 56674 55980 55731 55278 55018 55335 54404 54111 54106 54187 53332 53111 52899 52213 52575 51877 51274 50900 51170 51018 51470 50425 50522 49320 50205 49387 49924 48463 49268 48465 48455 47640 47978 46993 47846 46874 46117 46428 46525 45851 45967 46376 45110 45173 44961 44548 44576 44372 44653 43939 44125 43173 43070 42868 42430 42083 42313 42365 41512 41687 41453 41471 40527 40693 40587 40481 40423 39798 39650 39374 38645 39010 38457 38778 38919 38703 38159 38168 37757 37335 37863 37352 37018 36887 36679 36801 36975 36339 36354 36040 35645 35287 35064 35557 34893 34691 34563 34087 34129 33739 33512 33826 33082 33182 33064 32568 32869 32298 32680 32404 32251 32108 31685 31536 31744 30895 31040 30855 31087 30916 30847 30070 30734 30466 29848 30036 29704 29435 29491 29640 28932 29299 28613 28896 28508 28274 28319 28216 27900 27750 28013 27834 27202 27183 27442 26975 27306 27153 26897 26917 27001 26706 26198 25972 25884 25964 25825 25548 25764 25351 25147 25212 25151 24656 25012 24691 24469 24755 24669 24366 24285 24162 24092 23686 23999 23555 23364 23391 23778 23454 23097 22691 22442 22819 22279 22574 22566 22501 22153 22357 22275 21855 21564 21555 21598 21616 21105 21263 21237 21258 21214 20805 20796 20769 20537 20654 20520 20678 20350 19909 20245 20294 20053 19770 19988 19809 19665 19911 19469 19384 18779 19118 18870 18753 18737 18458 18271 18433 18304 18072 18158 18182 18273 17990 17840 17845 17703 18007 17511 17619 17554 17437 17402 17137 17086 16700 17339 17053 16966 16749 17263 17062 16564 16511 16336 16190 15864 16040 16142 16014 15835 15775 15950 15613 15620 15335 15751 15156 15401 15346 15112 15248 14819 14764 14909 14886 14823 14777 14587 14828 14694 14632 14306 14331 14540 14294 14494 13959 14105 13809 13761 13905 13903 13759 13896 13317 13591 13332 13243 13302 13250 12861 13085 12818 12944 12909 12758 12780 12522 12695 12588 12860 12654 12404 12380 12583 12256 12184 12174 12378 12152 12193 11991 12002 11946 12021 11846 11923 11795 11445 11535 11325 11529 11506 11218 11507 11259 11170 11196 10898 11215 11071 10905 10501 10867 10876 10902 10896 10892 10951 11300 10881 10700 10475 10503 10614 10518 10363 10301 10354 10104 10311 9987 10355 10001 10102 9907 10055 9845 9641 9438 9562 9535 9622 9404 9396 9401 9421 9448 9196 9378 9382 9350 9133 9071 9291 9029 9292 9194 8812 8866 9064 8579 8825 8559 8463 8512 8298 8510 8287 8508 8372 8341 8338 8532 8000 8181 8051 8045 7934 7943 8065 7756 8163 7887 7812 7684 7733 7657 7541 7678 7719 7746 7779 7541 7585 7561 7479 7463 7560 7414 7406 7317 7116 7133 7193 7302 6918 6896 7095 7139 7113 6873 6948 6813 6919 7118 6800 6667 6956 6604 6545 6699 6688 6611 6723 6687 6517 6595 6677 6360 6736 6513 6439 6272 6394 6230 6414 6147 6334 6292 6425 6324 6172 6317 6149 5959 6139 6171 6004 6089 6040 5904 6049 5977 5940 5870 5899 5865 5804 5895 5627 5748 5745 5682 5632 5647 5512 5550 5495 5633 5558 5486 5576 5408 5280 5246 5402 5400 5265 5243 5447 5473 5366 5229 5346 5263 5280 5280 5169 5211 5424 4958 5087 5264 5153 5052 5311 5016 4941 5014 5046 4842 4799 4801 4771 4773 4822 4622 4826 4794 4679 4931 4724 4722 4496 4584 4565 4404 4398 4434 4657 4505 4481 4564 4381 4436 4375 4528 4534 4379 4332 4421 4376 4308 4197 4248 4191 4261 4227 4062 4070 4106 4335 4162 4011 4200 4154 4157 4274 4084 4059 4074 3999 4042 3990 3911 3890 3930 3914 3790 3854 3786 3727 3706 3790 3731 3675 3782 3751 3633 3673 3711 3712 3555 3429 3587 3440 3400 3450 3421 3464 3633 3451 3458 3487 3466 3326 3347 3380 3360 3370 3488 3294 3247 3478 3263 3229 3178 3131 3198 3228 3240 3393 3207 3249 2957 3227 3141 2940 3058 2875 3091 2880 3023 2926 2944 2877 2966 3013 2972 2901 2888 2970 2836 2926 2803 2957 2798 2838 2979 3087 2776 2841 2814 2706 2792 2741 2976 2844 2662 2687 2647 2654 2605 2688 2663 2625 2636 2586 2579 2622 2560 2552 2590 2649 2435 2489 2502 2487 2571 2413 2543 2541 2555 2556 2385 2329 2330 2475 2319 2363 2302 2303 2372 2290 2204 2337 2268 2309 2312 2238 2218 2288 2303 2258 2195 2215 2114 2288 2235 2210 2245 2164 2197 2265 2201 2227 2127 2144 2093 1948 2050 2113 2136 2043 2007 2159 2042 1973 2065 1999 2028 1897 1972 2015 1952 2001 2036 1922 1990 1948 1954 1837 1821 1888 1805 1832 1877 1840 1917 1850 1840 1762 1816 1843 1717 1811 1736 1761 1758 1784 1803 1725 1757 1761 1716 1795 1648 1656 1671 1773 1853 1663 1712 1721 1662 1615 1739 1696 1703 1630 1713 1629 1569 1639 1641 1582 1619 1560 1598 1618 1654 1639 1578 1656 1576 1513 1535 1611 1501 1500 1532 1529 1548 1497 1445 1544 1470 1617 1419 1550 1529 1571 1433 1461 1486 1545 1446 1428 1457 1509 1424 1377 1412 1290 1515 1388 1516 1382 1342 1383 1308 1340 1292 1440 1409 1408 1316 1340 1381 1280 1296 1307 1282 1261 1346 1245 1265 1220 1217 1259 1325 1247 1268 1265 1292 1200 1189 1256 1158 1266 1263 1188 1291 1168 1287 1151 1180 1236 1141 1202 1193 1159 1138 1158 1154 1149 1073 1163 1054 1106 1101 1082 1146 1057 1024 1058 1125 1168 1105 1101 1111 1075 1060 1085 1088 1014 1093 968 1078 994 1137 1031 1049 1049 1040 1048 1067 894 1014 1010 1126 1040 1006 955 912 1042 924 919 931 912 885 959 963 906 939 955 886 963 908 942 957 923 975 882 872 866 840 939 901 914 900 850 905 924 869 893 874 807 863 852 854 926 786 825 857 828 864 849 842 816 874 833 865 833 809 856 784 815 806 765 780 782 778 771 773 808 754 824 767 749 754 772 742 735 706 788 734 757 751 758 760 686 724 701 686 788 706 747 732 683 739 632 661 682 687 681 669 632 692 579 698 654 791 674 633 648 635 597 681 671 585 597 600 647 633 602 616 578 664 615 680 626 582 679 647 649 643 645 652 625 645 581 640 629 603 592 595 622 608 619 558 570 584 582 580 584 548 585 570 605 555 581 554 598 572 599 605 517 623 577 576 553 592 587 582 540 621 572 653 585 590 545 548 521 549 608 546 518 527 650 525 578 541 558 547 548 522 536 523 529 500 592 459 460 438 449 492 486 477 511 457 480 454 477 485 494 467 467 432 481 445 456 462 432 432 440 454 427 455 476 497 443 487 467 433 420 460 393 405 406 407 420 477 380 449 401 443 440 375 418 412 395 420 428 433 413 370 363 399 394 397 409 456 451 416 480 382 423 388 390 401 361 408 424 430 402 459 405 397 368 346 436 379 419 370 404 428 387 353 368 359 365 359 376 369 343 352 326 347 361 364 393 356 366 363 354 341 355 340 398 341 376 320 362 343 399 344 356 308 364 318 368 331 302 348 314 327 290 329 324 289 299 319 315 331 300 334 307 290 302 274 326 309 323 277 303 277 276 285 316 346 335 325 297 313 288 302 307 233 282 265 356 319 304 284 276 306 281 259 293 291 263 345 305 317 282 289 302 292 308 290 279 237 287 263 254 281 258 251 300 301 317 300 271 278 279 235 263 262 227 281 261 243 257 259 286 276 245 234 299 267 285 275 276 239 242 241 251 246 228 232 235 301 252 257 259 257 243 247 261 242 211 208 213 222 230 200 229 200 238 204 195 213 227 234 220 210 240 178 220 234 248 215 210 249 221 222 234 217 264 253 174 196 195 227 262 220 217 247 252 233 194 223 200 225 217 225 207 187 185 210 219 160 182 203 209 178 211 185 179 192 166 195 167 160 186 174 179 210 183 191 204 164 192 202 179 202 188 162 197 161 169 164 158 150 180 165 193 163 177 144 166 171 194 150 167 142 207 159 149 157 179 171 168 138 158 171 172 161 148 166 170 146 151 179 155 142 155 139 171 144 142 164 151 166 132 122 133 132 140 155 145 188 147 142 167 144 172 130 167 158 142 149 145 200 143 156 140 153 132 137 130 147 115 187 123 145 159 136 130 149 136 133 150 132 117 150 120 179 119 150 124 115 140 147 130 141 122 119 122 130 132 118 123 109 135 138 119 135 151 114 135 127 125 133 122 115 135 160 159 149 129 114 115 128 119 148 145 114 129 123 145 142 116 121 132 121 124 122 137 122 131 150 152 102 117 146 118 123 120 138 110 127 135 130 117 116 137 113 108 115 98 99 99 102 93 126 95 122 119 104 116 101 113 105 124 132 94 118 97 92 112 122 131 122 108 109 115 122 138 93 110 111 96 101 116 87 97 100 116 79 114 106 93 92 100 108 104 112 85 109 107 95 112 105 101 111 116 91 94 113 93 128 102 119 95 116 119 112 105 
];
B = [
0 0 0
 402392 178476 223916
 219903 98420 121483
 731720 370889 360831
 416399 197594 218805
 256118 126214 129904
 676854 362784 314070
 500657 252952 247705
 257762 132443 125319
 835919 463821 372098
 847816 453577 394239
 165485 74953 90532
 2660537 1508241 1152296
 352443 176190 176253
 133653 60939 72714
 521473 337250 184223
 175314 102764 72550
 59894 30184 29710
 555969 359429 196540
 54218 26352 27866
 54659 28769 25890
 16896 8294 8602
 392 234 158
 9952 6063 3889
 823189 541263 281926
 59970 31184 28786
 69300 40913 28387
 827752 549579 278173
 46708 28414 18294
 105787 63883 41904
 1337641 891483 446158
 108523 65475 43048
 176681 114280 62401
 847999 591013 256986
 871787 648154 223633
 1449311 1116472 332839
 2157672 1604664 553008
 2692568 1865491 827077
 1299663 992082 307581
 2588600 1981669 606931
 1665272 1131188 534084
 77499 49714 27785
 2376785 1682857 693928
 37680 24078 13602
 71932 46553 25379
 2726482 1981119 745363
 72777 48236 24541
 1279438 893102 386336
 2468962 1925178 543784
 1275150 909776 365374
 18 12 6
 28176545 23453164 4723381
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
379 400 10 4
323 114 4 2
474 289 4 2
408 312 9 4
200 371 18 12
800 589 36 29
12832 892 380 343
72751 1233 1104 1131
323311 1847 2495 2459
970327 2979 5196 5225
1962880 4318 8400 8324
2874049 7202 13539 13468
3682851 11250 20008 19914
4864376 16973 31218 30929
5763241 26669 43441 42921
5062750 42505 54153 54351
3549891 57052 68425 68376
1938806 60528 77790 78164
787543 63120 85017 85326
326571 86218 116665 117381
232511 124689 143946 144005
196020 138402 161019 160426
234889 153549 184512 183366
238239 181481 200839 199816
257606 191096 215246 215213
256623 200318 220418 219853
252773 202880 219226 218562
242207 197576 210480 210765
223441 185564 194219 194749
199346 169522 175954 175340
176010 153897 156426 155977
154925 140199 138030 138435
136965 126792 122864 123803
127062 117454 113258 112694
117863 112052 106385 106639
111754 107544 102753 102286
109321 105021 99226 99322
102287 99986 94876 95596
94792 94044 90639 90288
90697 90064 85333 85996
84999 84512 80973 80679
77653 77452 75629 75461
71682 70723 69285 69881
64773 63426 62944 62948
57062 56987 56710 56429
50262 50181 50358 50731
44614 45123 44841 44961
39104 38881 39021 39005
33691 33662 33201 33121
28051 27944 28491 28945
22824 22766 22976 23144
17350 17330 17565 17495
12616 12773 12530 12849
8599 8737 8924 8795
5591 5546 5440 5326
3135 3163 3248 3129
1555 1491 1588 1596
584 583 569 580
163 182 176 172
52 66 47 35
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
