A = [
2255931 2225500 11636135 2342726 2397665 2288963 2208964 2371882 2307546 2427805 2627557 2903740 3449327 3910318 4251937 4578171 4978391 5358390 5423614 5372667 5594594 5765906 5710132 5620176 5712560 7150716 7262163 7218404 8397822 6919379 6875488 6720170 5241714 5306976 5252922 5213892 5168292 5032121 4978484 4946081 4875835 4873109 4837613 4790928 4826746 4708032 4633844 4720657 4587611 4532512 4495446 4322244 4340267 4323185 4207195 4091879 4117888 4132348 3976928 3876632 3871163 3807961 3742020 3656731 3603044 3573066 3484408 3411859 3369738 3293945 3238421 3215876 3162680 3124493 3114489 3058941 3009636 2977717 2904800 2833538 2791853 2758903 2690453 2638197 2621885 2548425 2473236 2379485 2321557 2282948 2234888 2187542 2155116 2113505 2077773 2047014 2009067 1979465 1943664 1909216 1877913 1840796 1805069 1773216 1743400 1718671 1688743 1662531 1638221 1612308 1584596 1570977 1549079 1524345 1513177 1491574 1740078 1740717 1725717 1969754 1975946 1950483 1921896 1892239 1861715 1827313 1794852 1762208 1730074 1700716 1665829 1634132 1601278 1572474 1542930 1513438 1484462 1462484 1435428 1406921 1381247 1355972 1329669 1304324 1280787 1255471 1234654 1213507 1188172 1161594 1141399 1119960 1101063 1075698 1056627 1035273 1012621 992400 973767 954274 939126 919291 901742 886552 866104 848524 832354 817852 804140 789216 774575 760341 747316 731792 720787 706481 692339 680490 666638 654436 641369 631068 622141 609541 598626 589527 575717 569401 557614 550346 541183 530826 523150 515046 504620 493508 485460 477249 470347 460709 454612 447787 440124 431769 426497 418821 410988 404430 397017 389584 380457 373033 365684 359812 355694 349875 344110 339259 334149 329534 324155 319533 313792 307808 300297 293310 285102 278168 272459 264486 256705 252117 248292 242242 237024 233794 229521 224137 220490 216569 212826 208996 206175 202096 197658 195197 191367 187537 183849 180866 177248 173481 170595 166678 164670 162025 158956 155451 152033 150434 147879 145055 142580 139538 137026 134499 131577 129925 127657 125281 123235 121232 119008 117269 113837 112368 110225 108429 106641 105244 102881 101478 99546 97993 96554 94535 92603 91486 89527 88471 86141 85924 83976 82192 81355 79918 78380 77456 75870 74388 72629 71755 70158 69051 68230 66994 65789 64967 64058 62489 61661 60787 59440 59189 57460 56591 55471 54715 53489 52872 51886 51447 50473 49709 48650 48054 46831 46078 45838 44530 44231 43134 42564 41723 40627 40643 39555 39176 38506 38112 37762 36737 36109 35729 35244 33985 33749 33920 32547 32130 31610 30932 30466 30344 29917 29184 29094 28494 27901 27147 27111 26707 26212 25875 25614 25127 24707 24150 23974 23502 23042 22811 22397 22235 21665 21331 21002 20846 20438 19975 19778 19071 18991 18802 18477 18233 18135 17668 17247 17014 17066 16522 16363 16113 16075 15448 15140 15139 14776 14661 14278 14390 13965 13865 13424 13453 13354 12930 12516 12632 12340 12045 11868 11971 11829 11432 11366 11136 11122 10964 10732 10384 10408 10185 9908 9912 9836 9627 9475 9175 9152 9038 8963 8905 8743 8453 8222 8331 8086 8092 8122 7860 7889 7644 7455 7360 7307 7127 6956 7034 6824 6769 6807 6655 6508 6330 6107 6225 6231 5859 5969 5876 5716 5582 5512 5449 5416 5438 5284 5332 5177 5093 5079 5056 4955 4845 4781 4796 4613 4489 4417 4476 4338 4350 4259 4271 4259 4044 3950 4027 3981 3930 3896 3840 3853 3556 3648 3525 3598 3549 3552 3376 3439 3380 3391 3362 3183 3104 3117 3074 3054 3141 2955 3034 2864 2933 2836 2734 2704 2692 2649 2608 2647 2616 2530 2453 2490 2502 2348 2412 2330 2321 2338 2301 2168 2214 2180 2094 2126 2141 2098 2106 2065 2039 2030 1966 2010 1920 1927 1887 1963 1919 1794 1737 1778 1726 1767 1723 1733 1686 1644 1559 1629 1597 1586 1639 1521 1507 1578 1498 1435 1477 1400 1434 1451 1385 1408 1346 1360 1296 1312 1354 1324 1259 1308 1286 1274 1252 1211 1211 1201 1185 1215 1179 1215 1230 1203 1105 1138 1031 1074 1111 1084 1052 1093 1107 1062 995 1034 1074 1007 987 950 966 1002 882 935 943 964 878 944 937 872 880 894 859 851 932 808 812 780 825 792 773 777 805 761 711 758 761 793 745 780 716 691 687 686 657 684 730 688 679 704 719 672 691 657 687 644 616 592 684 591 620 680 617 598 582 598 548 591 570 632 584 582 556 562 560 501 547 517 563 544 522 446 542 537 516 527 475 507 457 498 479 479 507 496 471 456 435 489 480 457 476 486 494 460 473 445 459 420 434 480 427 489 433 417 394 443 384 393 429 414 411 415 438 389 387 434 415 412 388 411 399 407 365 386 389 421 402 399 346 373 343 343 334 344 351 352 372 317 348 343 320 330 330 343 351 284 324 329 289 361 335 322 302 284 286 290 301 292 317 308 306 291 284 280 275 286 276 273 297 282 255 271 252 270 295 264 236 255 252 251 249 243 263 239 250 257 246 275 224 245 240 223 244 225 252 249 241 243 232 248 235 274 246 249 220 214 223 218 239 238 214 236 242 200 204 187 210 209 216 230 210 201 242 218 198 212 201 205 194 213 199 176 203 187 175 209 211 191 194 180 192 203 182 194 183 175 208 195 174 199 207 165 168 186 183 184 163 211 190 158 168 175 155 191 171 152 146 164 159 181 159 162 163 173 161 151 177 145 163 153 138 156 155 138 142 129 131 133 145 149 134 160 138 134 142 175 140 190 162 143 143 138 178 137 156 146 154 152 131 145 154 148 136 137 132 133 134 142 126 148 118 148 118 112 118 143 120 118 128 122 111 116 116 120 134 125 116 110 100 135 117 116 115 125 121 130 102 119 114 111 114 123 105 103 117 92 129 100 95 101 88 91 103 96 106 95 109 94 107 98 102 90 90 94 93 93 109 86 97 87 96 105 106 95 81 75 91 90 91 81 89 82 97 98 106 104 96 88 100 79 88 68 91 85 91 90 79 88 79 94 104 75 77 88 111 91 85 81 72 100 89 63 73 95 80 55 73 73 82 79 65 85 79 83 79 71 74 97 93 108 149 218 250 278 299 307 295 327 335 305 344 369 249 209 193 216 233 215 193 193 210 163 197 190 192 167 191 189 165 171 219 176 226 188 195 216 195 193 197 164 185 194 208 180 220 195 191 211 218 235 249 238 286 253 254 279 286 268 254 239 281 303 966 324 307 254 257 174 183 203 135 126 144 122 122 135 146 112 137 131 124 107 110 117 96 125 113 106 84 107 91 103 111 110 130 114 127 97 106 106 123 136 138 160 244 333 1577 1288 1059 719 631 547 534 525 368 300 265 187 183 209 225 191 188 167 162 103 112 86 85 113 167 657 76 65 69 58 55 50 57 51 47 36 37 39 51 53 40 48 42 48 48 28 49 38 39 55 47 53 61 57 55 52 48 67 68 63 65 56 71 61 62 53 80 60 65 62 60 60 68 59 69 80 83 92 60 72 83 84 77 85 79 100 88 88 81 77 96 85 100 93 102 111 102 109 99 72 101 95 78 90 99 112 85 116 96 92 101 99 94 90 128 124 109 101 111 242 116 98 96 105 154 113 114 114 132 125 106 105 115 108 104 117 128 114 128 99 114 115 107 83 131 98 104 122 127 125 121 127 130 119 124 123 88 102 115 110 100 110 105 129 98 85 85 78 59 62 57 61 65 59 81 69 147 54 115 198 74 76 59 54 43 55 45 47 58 60 66 48 50 62 55 53 50 53 53 63 63 79 69 57 53 53 55 48 64 72 54 75 67 70 84 81 75 58 58 61 56 79 67 51 60 59 62 54 54 55 73 62 71 60 51 64 76 84 72 76 80 57 64 83 89 73 74 82 63 58 56 48 52 48 53 49 44 38 47 203 66 43 43 50 45 43 39 44 42 41 44 36 38 32 26 40 42 36 37 26 36 36 29 37 25 35 50 31 47 36 42 31 16 23 33 27 25 22 33 19 25 26 32 23 28 28 16 25 30 28 26 32 23 25 25 29 29 33 44 31 29 23 37 30 32 31 29 36 32 46 54 46 28 38 30 27 31 28 19 34 29 33 24 18 18 24 25 12 27 15 16 16 19 20 26 23 19 24 25 19 19 20 18 20 28 26 20 33 18 29 25 31 42 31 37 37 26 29 36 36 29 38 42 31 32 37 31 34 29 43 45 28 32 30 26 26 30 38 38 19 27 36 36 27 25 26 40 33 35 45 29 33 37 36 41 29 42 30 33 28 27 28 36 35 32 32 30 33 34 41 33 39 36 37 42 27 30 26 17 27 32 25 33 29 30 24 35 31 24 31 30 25 15 23 27 29 27 35 29 22 23 25 24 22 19 30 39 47 34 38 25 48 42 35 29 23 30 21 34 26 24 31 34 33 23 20 24 22 18 20 19 18 16 10 19 12 17 16 20 19 9 14 8 16 18 16 22 20 17 19 16 12 18 22 15 20 15 8 19 5 20 12 15 10 14 13 24 26 9 5 15 15 13 10 14 14 11 20 20 14 11 11 11 13 16 16 5 17 12 4 16 11 9 10 10 9 12 8 5 12 5 11 7 17 7 6 5 7 9 9 12 11 8 5 7 8 10 12 11 6 6 9 8 7 9 9 10 7 10 8 14 6 3 11 4 9 12 10 6 6 7 9 10 11 9 5 4 6 10 10 11 10 8 12 9 10 7 18 7 8 17 7 11 6 6 13 9 11 8 17 7 9 5 5 15 12 9 11 10 8 13 4 4 9 9 7 8 9 7 6 10 11 8 7 9 6 4 10 1 11 6 7 8 6 8 10 8 7 1 5 8 3 11 6 7 10 3 9 7 14 9 6 7 10 13 7 11 10 8 3 8 5 6 6 6 8 10 6 6 6 9 8 9 8 11 11 5 7 7 11 13 11 6 6 8 8 9 9 7 8 8 13 11 16 13 10 6 15 17 12 9 9 10 16 11 16 14 6 9 9 10 12 11 10 8 12 10 4 9 13 8 11 9 11 8 5 12 13 3 4 7 7 4 8 5 9 7 9 12 16 13 18 10 8 15 11 19 16 10 7 8 5 6 9 10 6 7 10 7 6 9 8 5 8 6 9 5 4 4 5 5 11 7 9 6 2 6 2 5 11 1 4 9 5 5 4 8 7 7 9 7 1 6 7 5 3 2 5 3 11 5 2 8 5 5 4 11 4 5 9 6 
];
B = [
0 0 0
 2218136 1432653 785483
 2080628 1393996 686632
 2526757 1773346 753411
 2193653 1533963 659690
 1553225 1099936 453289
 2231111 1642122 588989
 1311287 970056 341231
 1827391 1369533 457858
 1966036 1445866 520170
 1455775 1057540 398235
 3072851 2307726 765125
 1584360 1178391 405969
 1151510 846923 304587
 1941969 1477582 464387
 1406193 1063080 343113
 1046310 790078 256232
 2182312 1698969 483343
 992832 759167 233665
 1028272 790454 237818
 1077532 832474 245058
 1020072 789792 230280
 1017471 792241 225230
 2898166 2274457 623709
 1126258 879085 247173
 1279544 1003256 276288
 2851323 2248442 602881
 1368895 1083103 285792
 1128643 890148 238495
 3776533 3001313 775220
 1339615 1060774 278841
 1386364 1106407 279957
 3037571 2437500 600071
 1395468 1119039 276429
 3587402 2901692 685710
 1558055 1256484 301571
 1524384 1230527 293857
 6717300 5515721 1201579
 1879626 1534523 345103
 2605003 2145712 459291
 6304428 5191842 1112586
 2618295 2158967 459328
 3687715 3046985 640730
 4111301 3385683 725618
 2140596 1767975 372621
 3165251 2615193 550058
 4574924 3790540 784384
 2992930 2478396 514534
 1311738 1073693 238045
 8261266 6910224 1351042
 1309683 1075236 234447
 2557824 2124427 433397
 10490378 8845581 1644797
 2396709 1996412 400297
 1038895 855205 183690
 16608872 14120138 2488734
 1521929 1268327 253602
 959589 792757 166832
 1523139 1274034 249105
 748823 617258 131565
 119745153 109262415 10482738
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
17 72 0 0
5 9 0 0
6 25 0 1
18 45 2 0
16 33 2 0
30 37 391 14
840 65 1150 101
7759 69 1442 320
362875 95 1931 605
3209404 142 2767 1120
6326940 198 3275 1748
10555619 324 4535 2909
14618689 556 6606 4833
18007760 1048 10547 8359
17984771 2177 15549 13940
15215163 4938 26381 25180
9919180 9001 43177 42651
5399860 15004 64221 64196
2814018 24770 89805 90555
1311450 39250 117369 117367
572281 61036 146597 146755
293237 89288 177450 177804
241339 130590 213164 214456
270738 181066 254372 256120
316704 241462 300575 301433
367076 306611 351505 352686
420865 373934 405019 405532
474989 437536 460062 460884
523233 492523 509343 510558
563433 539560 551159 555282
595336 576417 585777 586172
613388 601224 607163 608925
625331 615243 619233 622498
629825 624531 626300 628973
634235 629343 629030 630889
636715 632723 632851 635721
635812 634123 636132 635746
641273 639961 639017 640225
646988 646782 645124 646830
653201 653236 652419 654462
663731 663308 664086 665109
680463 679711 678447 680635
698987 699767 698662 701478
725696 723767 723890 723880
753979 755467 753131 756238
788705 788529 785545 788332
821131 821561 821092 822175
851769 852683 850659 852791
878750 880258 877810 880263
901796 903533 900653 903337
914725 917171 916885 917057
918409 920707 917639 920969
909963 911454 908389 910530
892679 897357 893439 895600
862699 864306 862245 865288
825002 827512 824241 827099
776123 778047 776808 779934
721021 723385 721737 723167
658136 659272 657638 659681
598763 600571 599205 602071
541497 540672 541907 542214
491923 495300 492791 494523
442676 442290 442637 443596
409176 408721 409086 409931
385010 385527 385008 386743
372225 371972 370085 372265
367953 368987 368518 372128
367815 369906 367065 367703
352543 351389 350495 352632
356550 356512 356514 356833
347272 348650 346711 347687
329633 328217 329166 329822
309568 309877 309116 309068
267024 267712 266577 267499
225726 225883 226292 226312
186261 186081 185663 185969
139207 140277 139257 139291
90432 90881 90238 90594
69333 68827 68980 69124
50819 50745 50628 50684
28491 28544 28401 28195
13875 13747 13964 13596
655 677 645 662
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
