A = [
2318192 3144587 3384550 2073207 4146632 2511682 2507901 3569409 3124382 3598818 2425627 2741710 3372334 2709336 2843371 2501001 2792628 2727542 2681568 2607431 2468845 2838178 2664189 2580897 2700374 2459914 2469095 2596868 2731210 2582842 2572823 2711946 2619925 2377701 2297103 2568145 2796234 2429956 2664562 2772423 2418101 2325950 2204347 2497482 2250185 2318637 2398541 2255814 2363776 2175434 2131984 2290531 2202669 2251442 2157597 2115564 2195039 2006080 2033529 1991998 1989953 2050372 1985293 2021257 1971913 1909608 1992867 1898274 1956490 1875748 1959336 1948417 1824095 1864829 1809569 1884127 2013575 1941397 1960352 1969219 1912321 1871084 1812908 1827837 1779827 1797722 1761799 1679775 1654188 1642336 1644213 1645104 1618684 1607697 1600368 1578721 1569660 1548919 1527717 1503256 1493285 1493137 1497095 1488187 1467134 1480955 1449621 1443371 1434088 1418543 1414155 1395425 1388495 1379975 1358896 1369834 1360878 1355911 1356042 1337837 1346834 1319393 1320712 1299788 1294542 1289904 1270326 1267484 1256461 1248228 1231440 1216528 1216261 1210537 1204192 1205370 1179932 1178470 1171316 1178664 1158986 1147260 1142516 1134963 1123067 1113023 1104419 1093216 1099816 1082865 1082118 1063244 1056007 1053038 1049526 1046749 1040072 1024323 1033604 1021966 995234 999341 997081 986481 987095 979195 978414 972274 953509 954617 937240 939440 934544 935922 923405 916682 914769 904163 907326 900890 898928 891418 874850 868962 870832 869973 860881 854257 851269 844792 828168 823914 818552 821769 811284 803104 798626 788254 776950 767842 762785 767471 752374 754674 752840 742852 748381 732049 722687 723391 711236 719533 710084 708489 697894 685357 674398 678419 666407 657421 659786 648534 648642 646505 634396 632368 623976 617020 616422 609166 612464 606650 594742 602481 587433 587621 586968 580524 573597 574947 564762 566115 558185 556557 549294 549241 547612 541050 537741 534544 528649 520185 524559 517035 513656 514958 506269 503529 500343 500698 488530 485467 489269 489899 478083 475057 475191 470831 465816 464919 461780 456508 456943 445465 447973 442028 439101 435095 431661 428944 430333 429346 418447 416632 418098 410084 407506 407620 398197 400738 404805 397124 397372 388670 387901 387663 386859 378335 382645 374949 369852 374478 367364 365915 360731 368080 359882 348228 348574 349582 343933 350226 347652 342086 332524 334782 337439 330298 332067 327073 324948 326288 320955 324685 320288 316170 313933 310820 306266 301816 305066 302157 302094 292938 294289 294706 292477 286395 285855 283102 286985 282448 284977 278362 279357 275647 276520 269835 267161 264790 269869 260523 264305 264103 260674 262096 257667 254390 258858 250195 248614 253291 251494 248838 248061 247469 243453 242440 242953 239048 238967 237329 236192 230256 235172 231039 230065 227329 226340 225614 233169 222482 222348 222053 223419 217017 215079 213357 213025 215618 218605 212410 212803 207407 208649 202622 207893 211364 202254 204973 204731 200833 199947 197052 196747 193528 195680 194962 193428 197942 191324 189109 186350 190187 188219 187520 184967 183132 184851 184550 182844 177882 176350 177592 175184 178225 175981 179348 174889 179194 175429 167144 172774 170294 168882 171979 170027 173108 164342 164911 162335 160880 165453 161105 164888 157994 158894 161971 159103 159434 156275 155611 153782 152642 153694 153338 151995 150673 149595 145674 150090 146886 147732 148108 145256 145717 143160 142841 142422 138506 142915 142746 138087 139256 139814 137968 137612 135575 138225 134593 136806 134805 136148 135381 129799 131353 130980 132843 129542 133994 133933 129633 127706 132218 125311 121236 123152 125718 120784 122660 122462 122803 120345 121387 121161 120617 123565 120201 119525 120923 114888 118741 116080 116396 120057 111110 113909 113370 110348 110989 111450 109036 111954 108253 107951 105319 107633 107097 104993 104001 105520 106186 105225 102095 100647 103978 103648 100086 101334 101689 100706 98006 94363 99765 95876 95298 96288 98760 96814 98809 95016 94324 94675 98002 95742 96007 92464 96356 91386 91039 91967 90153 91459 89121 88007 91850 89156 90779 85049 88432 85364 84410 85145 86429 85525 84463 86303 83261 83415 82469 84878 84628 82085 79306 81804 79937 79486 80030 85036 78962 78951 78773 75491 76395 79396 76545 79689 75812 76357 75596 74945 75432 76718 76451 72851 74874 74744 71926 68987 79727 69786 72747 72186 72667 71217 68748 72123 74672 69612 70325 67939 68070 68572 66472 67254 66537 64593 66463 66587 66378 65838 64387 63052 67549 63516 64757 61189 64229 61564 61940 61242 62219 61997 63097 60356 58185 60012 61149 60794 59278 60551 59287 59692 59791 60095 58339 58764 57925 55283 56895 57386 55180 56276 56396 54931 55478 55240 53440 53236 52448 54087 53431 53282 54169 51853 53009 50477 52065 51232 50735 51007 51031 49547 51835 49594 50792 48731 50319 49413 49461 48669 48958 49801 50325 49712 49580 47056 48973 46988 50021 46512 44757 48035 46932 47017 46683 47154 45023 43188 46888 45966 44396 45562 46263 44663 45472 41987 41923 44827 44461 44481 42290 43518 42780 43527 41170 43878 43543 42425 41422 41357 41217 38662 39661 40107 40031 40086 39026 40036 39209 39782 37955 39229 38887 38473 39542 38475 37073 37768 36216 38428 38061 36113 38851 36388 35486 37596 35611 36818 35873 36475 35157 34399 36051 36536 33673 32296 33698 34581 34637 35075 33157 34606 35802 33671 33113 32527 32391 32639 32357 32703 30995 32845 33197 32740 31251 30459 31202 30951 31285 30467 31032 30828 29172 30139 32128 30715 30834 30456 29985 31037 28692 30464 28551 28547 28707 29847 28362 29179 28883 28381 26736 28208 27582 27481 26905 27165 27135 26935 29155 26718 27183 27577 25826 25331 26714 24946 28391 25499 27917 25607 26862 25816 24492 25931 24112 23297 25363 24782 24802 23203 24133 24372 23791 24291 23777 22859 24387 22484 24076 23267 22968 22801 22245 22349 23075 22395 23538 23199 22927 22676 20693 22233 22634 21781 22742 22643 20341 20979 21458 19900 21939 20370 21270 21946 19599 19616 20844 19060 20150 19674 21232 19863 20459 19631 20434 20124 18348 19430 19496 19428 18300 19304 18159 20429 17885 19091 18991 17890 19215 18436 17980 17460 18078 18070 17416 19039 18506 17509 17729 17943 17668 17938 16856 17283 18072 17283 17683 17517 17287 17342 16966 16064 16469 14943 16134 14737 17511 15584 16686 16386 15316 16554 16258 15506 15330 15407 16281 16161 16066 14077 14768 15713 14378 13849 15545 15402 13949 14032 15081 15218 14080 15146 14704 15113 14399 13660 13574 12908 14021 15187 13657 14300 13575 13610 13359 13730 14050 14382 13471 12344 13661 13041 13750 12836 12070 13037 11848 12099 13483 12655 12494 12791 12909 13375 13737 12914 13469 12203 12484 11981 11679 11735 12275 11531 11980 11354 10983 12008 10694 11568 11400 11663 12353 10264 12703 10773 11965 11193 11127 10269 10874 10960 12277 11216 10858 10282 10439 10921 10669 10857 10314 10701 9729 10298 10066 10614 10401 10582 10283 9555 10336 9445 9964 10266 9513 10598 10806 10625 9950 9541 9291 9218 9650 9690 9474 9079 9935 9103 10543 8844 8808 9384 9499 11181 8379 8231 9143 8968 10235 8168 8908 8835 8907 8550 8488 8504 8246 8543 8193 7978 9401 8375 8528 8719 9043 8250 8162 8655 8354 8224 7606 8708 7879 8534 7563 7063 8226 7907 7716 7962 7531 8063 8044 7776 8022 7630 8003 8023 7414 7564 7371 7711 7699 7117 7083 7596 7888 7442 6231 6611 7517 7131 7012 7223 7396 6831 6454 7473 7004 6775 7203 6871 7759 6770 6746 6274 6249 6502 6527 7145 6995 6814 6417 5758 6325 6224 6154 5772 6262 6484 6284 6965 6421 6176 5863 5850 5403 5404 6550 5762 5827 5353 5323 5868 5600 5782 5649 5948 5769 5909 5620 6441 5659 6713 5854 5518 5425 5638 4733 5023 5181 5663 5746 5666 4918 5395 4988 5105 4992 4832 5442 5548 5112 6329 5127 5241 5570 5021 5676 5119 5064 4691 4648 4734 5291 5717 4058 4719 4864 4829 4972 5283 4387 5332 4174 4792 4688 4509 4332 5021 4579 4477 4697 4402 4059 4361 4459 5238 4560 4182 4402 4445 4160 5507 4147 3966 4478 4120 4213 5161 4076 4304 4242 4386 4381 3965 4413 3606 3983 3671 4177 4216 3583 6098 3960 4128 3908 3909 4010 5037 3644 4061 4177 3827 3911 3349 3641 4186 4125 3634 3550 3575 3859 3594 3978 3503 3636 3427 3614 3743 2970 3646 3494 3532 3707 3175 3494 3043 3269 3603 3384 3253 3156 3334 2821 3244 3372 3288 3520 2927 3382 3172 2930 3249 3466 3218 3399 2985 3081 3354 2736 4140 2872 2765 3409 2838 3595 3123 2907 2833 2873 2955 3364 2987 3101 3334 2842 4788 2939 2969 2557 3035 3813 4277 2769 2711 2554 3347 3124 2614 3792 2626 3710 2436 2507 2763 3528 3105 2347 2268 4143 3687 2828 2871 2772 3682 3119 2240 3359 3644 2343 3826 2419 3072 4119 2425 3486 2855 3144 4065 2645 4118 3048 2907 4719 2886 4258 2659 2847 2786 3362 2512 4326 2778 2398 2154 2522 2347 2748 2432 2558 2011 1845 2313 2051 2019 2223 1949 2187 1919 1953 1640 2222 1696 1644 1874 1945 1888 1961 1799 2090 1817 1934 1682 1981 1920 1955 1577 2136 1659 1878 1791 1942 1553 1698 1575 1498 2125 1900 1574 1962 1597 1889 1906 1733 1834 1644 1562 2023 1661 1833 1537 1620 1674 1554 1671 1678 1087 1776 1512 1796 1563 1551 1678 1757 1659 1647 1607 1565 1692 1455 1642 1446 1267 1300 1329 1473 1313 1400 1421 1668 1571 1587 1327 1475 1132 1717 1510 1296 1335 1293 1254 1172 1166 1467 1526 1409 1286 1323 1614 1241 1096 1273 1427 1396 1240 1333 1497 984 1329 1137 1476 1320 1476 1354 1320 1237 1149 880 1155 934 1508 1412 1289 1168 1300 1314 1340 1426 1243 1118 1045 1167 1313 1117 964 1364 1058 1426 1165 985 1038 1096 973 1483 944 1111 1335 1038 953 965 1056 787 834 1029 1071 955 1203 808 859 807 932 1008 1221 926 1274 1073 1270 1172 933 865 853 1119 752 883 999 887 897 764 1163 828 1094 782 1164 917 929 733 681 1043 590 1030 741 926 794 709 742 857 931 856 655 1286 752 788 793 570 767 734 816 925 1020 1181 988 822 596 746 833 627 700 893 850 1025 563 748 932 621 797 737 839 994 671 851 920 728 758 813 963 580 832 801 792 682 844 640 797 534 1034 653 924 850 740 674 941 828 659 670 753 617 611 655 679 618 446 743 712 719 802 645 710 618 460 745 600 595 642 664 494 446 349 489 608 728 769 541 752 516 707 538 726 653 417 590 554 458 452 597 686 409 677 574 546 565 740 413 505 559 461 500 671 463 724 458 330 387 523 367 633 567 640 403 434 507 481 489 494 522 600 564 420 474 522 468 416 507 549 292 450 556 540 451 414 467 498 601 377 360 364 669 384 469 374 453 392 461 566 424 393 335 415 352 371 360 553 462 366 467 328 272 401 411 374 448 386 370 254 352 497 326 465 312 407 404 360 342 318 446 353 314 253 421 431 235 376 354 395 209 329 313 382 323 396 587 308 322 314 324 288 245 479 243 338 300 370 532 282 268 289 386 177 253 314 282 332 292 370 266 264 286 153 295 491 306 255 414 328 163 338 222 325 414 255 256 292 272 229 211 267 369 331 336 202 230 256 301 212 152 235 309 244 315 305 295 354 331 231 370 213 162 231 148 205 274 334 165 194 177 263 277 179 225 149 201 310 243 269 224 118 284 348 168 204 189 182 227 335 97 234 313 158 242 254 151 265 310 214 142 252 250 223 374 212 278 222 266 146 252 306 202 281 249 132 197 187 163 300 243 161 268 132 268 242 154 361 135 330 154 192 203 89 142 227 246 189 152 242 187 184 234 250 206 308 248 163 365 203 207 191 159 145 261 224 64 215 132 183 156 109 114 133 114 133 113 199 155 152 142 145 211 82 167 271 131 172 255 141 135 85 219 190 117 146 159 187 128 134 188 178 79 208 61 225 142 157 221 135 147 156 123 220 119 165 199 178 137 156 133 161 114 94 58 
];
B = [
0 0 0
 542397 430886 111511
 1161715 938501 223214
 866165 692559 173606
 792103 631148 160955
 706594 553450 153144
 635141 504995 130146
 520492 407392 113100
 502714 403815 98899
 481603 383068 98535
 799902 654795 145107
 527636 436183 91453
 560072 472717 87355
 562701 471573 91128
 547113 462599 84514
 765672 655834 109838
 662187 565769 96418
 684653 585604 99049
 665751 569170 96581
 697153 604708 92445
 790953 680683 110270
 696501 600344 96157
 721980 627535 94445
 739079 642873 96206
 732602 638922 93680
 852944 739364 113580
 768388 665590 102798
 839345 730346 108999
 769515 675481 94034
 807469 703181 104288
 858105 744983 113122
 876540 760608 115932
 881262 765135 116127
 819010 720109 98901
 1073336 926714 146622
 866707 763609 103098
 864149 755313 108836
 2227826 1906069 321757
 859981 759782 100199
 1066816 931311 135505
 1959944 1688604 271340
 1056044 923156 132888
 1785958 1543548 242410
 878120 777350 100770
 1072163 937900 134263
 1844053 1596837 247216
 1070363 938099 132264
 1797339 1557916 239423
 1064303 936977 127326
 1737816 1506684 231132
 1073350 938603 134747
 1708825 1485372 223453
 1115914 980891 135023
 1723680 1502514 221166
 1092095 962023 130072
 1857022 1613829 243193
 1646028 1441165 204863
 1030092 911547 118545
 1627918 1420872 207046
 808847 725896 82951
 173075035 158737337 14337698
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
226 307 0 0
17 83 22 0
0 212 0 0
0 463 1 2
14 476 6 2
51 1125 16 0
77 1224 91 67
1238 2244 105 133
88515 3452 191 167
895191 4567 482 408
1835375 7092 759 687
3054385 10899 1367 1934
4386077 14798 3772 3186
6101973 21665 8008 8066
6880822 31526 17310 17395
11238230 56430 34005 34376
20841973 107005 70783 71086
18035031 192517 126120 122617
9505276 299753 183242 185696
1243402 415206 252164 250037
380042 505311 314808 319164
426902 588060 398216 405279
452864 704789 480633 477598
525939 760061 558903 563022
579149 825193 621130 617341
625016 856692 669525 675497
668967 858634 707390 712663
696109 828737 719259 718095
703936 781309 712619 717982
702714 725609 693850 688530
676110 676320 657346 659983
637789 611805 615583 616208
590783 579123 580974 584091
563018 547579 554283 554615
547879 524372 525874 526319
534593 511460 517133 523062
537622 517245 522656 522146
534374 524013 527736 523805
544695 533924 541350 541211
566739 558272 556212 561075
591748 575825 581444 589857
633292 611369 617484 617117
669485 657038 663194 662661
724293 701084 712062 712152
773246 752303 755075 761585
810931 794678 806309 810376
854515 830769 846855 850473
879297 871312 876820 884466
907440 884153 896068 893513
905042 893703 893683 899150
881796 873116 880301 883957
846649 840198 841253 849496
799838 788333 793017 791331
736194 730413 730785 734052
664028 660558 659944 660527
585902 589465 599438 599339
519012 519811 519326 525994
457583 462561 463244 457544
400307 402139 401960 402582
358799 353046 352841 354353
318186 320073 319250 315956
293699 293601 291006 292551
273991 273358 270001 274721
264022 266354 262378 263348
257679 254656 255077 255928
249493 257133 253088 253407
258564 257454 257134 261185
266627 262833 269276 266117
275758 274203 271127 276202
288186 292521 288978 293940
306089 306047 301950 304665
315823 311138 307981 315785
312694 308866 310067 313088
283159 284239 284381 285403
250689 246535 251047 246038
204275 203666 205764 210720
157891 158128 158097 155963
109048 108237 109921 110609
84265 85509 85629 84902
57813 57549 55957 57234
34594 34436 34515 33448
15224 15289 15144 14587
710 908 1018 1010
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
