A = [
1099797 1472749 1566340 955601 1899261 1170171 1159992 1678114 1426114 1689342 1179214 1229871 1599359 1283210 1303963 1184796 1311806 1282359 1266231 1247334 1183210 1326027 1248099 1223229 1267260 1173851 1174305 1202413 1273531 1204938 1203630 1262447 1217095 1134622 1095866 1204572 1293414 1149598 1237595 1281844 1136851 1099200 1056419 1154719 1068576 1092584 1117802 1064802 1102987 1029622 1016738 1075218 1031934 1058651 1026083 998266 1032523 962525 975756 949807 947460 971172 937699 955278 932999 912686 938965 906171 925202 894850 920618 917989 870112 883709 860833 880089 926298 906154 906750 910006 887245 872285 854636 856877 833274 841158 829746 796027 786000 779163 778290 776285 767037 762085 756459 752742 742745 733429 724964 713555 712647 709796 709933 705923 695765 697566 686695 680592 676989 668663 666856 659104 655008 650275 643173 642751 641311 638538 637709 629294 628438 620820 619081 613596 608349 604700 597559 598049 591058 583589 580951 574540 573959 570354 565840 565677 559308 555950 551773 549213 547526 541544 535790 531765 526485 525917 521042 518101 514908 510909 506344 503363 498227 493925 493252 490070 488396 483384 480735 477218 469383 467959 468142 463563 463115 460900 459197 456078 450236 446207 443830 444206 439315 440133 435717 431323 430531 425997 425246 422393 419860 419993 413634 412753 409025 406147 405035 400212 399468 395791 388320 388503 383330 384132 378862 373509 373328 368567 364206 361992 357419 358250 352559 355634 350372 347555 346148 339397 336600 334781 334539 332213 328100 326219 325631 319750 315958 313858 310352 306516 306689 301725 300767 302693 293347 292894 289381 286712 288744 282014 282009 280296 278609 277229 273670 272221 269903 267992 266307 266489 262876 260934 259589 256709 255700 255841 253275 252038 248889 247157 245627 244412 242373 241402 239555 238218 235941 235422 234295 232447 229382 227914 227120 227793 224607 223294 222756 219956 219138 217773 216784 214476 214001 212249 211146 208942 208139 206592 204651 203086 202482 200822 200507 198367 197782 197122 194783 194838 192691 193077 190168 189352 188244 186180 185910 184796 185025 182516 181184 179442 178860 177940 175938 175629 174080 176708 172042 171119 169873 169533 168026 167614 168305 166324 164189 163225 162209 161040 160215 159338 159207 157035 156967 157744 154551 154204 151772 152537 150513 149189 149020 149530 147666 146281 144915 144853 144045 142674 141868 139976 140444 139275 139204 136867 137828 135566 136334 135428 133026 132898 132080 130775 131518 129819 129936 128799 128520 127315 126459 125970 125343 124749 124142 122800 123424 122265 121382 121676 120051 119733 118771 119144 119044 116802 116030 115282 114601 114372 113076 112953 111475 112013 111771 110715 110419 109205 107970 107957 107283 107642 105933 106003 104831 103643 104666 103035 102917 102196 101811 101283 101021 101031 99293 99612 98897 98550 98054 97281 97030 97866 95898 95091 94266 94583 94283 93869 92369 92321 92575 91390 91753 90612 90556 89630 88961 89858 88622 89534 88329 91780 87374 86530 86440 85860 85310 88686 85491 91103 83629 82550 83619 82497 82720 82364 81040 80497 80309 82352 78914 80037 78627 78937 78129 77096 78371 76530 76120 76650 75327 76076 74894 73325 75965 74126 74103 74133 72753 72725 72573 71611 73302 73376 70393 70002 71076 69751 70168 69053 71346 68903 68997 67161 69805 67122 66730 67815 66505 65985 65257 67609 65428 63881 63830 67349 63995 62569 61315 63603 62570 62485 62069 61418 60962 61645 60219 61532 61541 60259 59515 59471 58900 59190 58483 57945 59834 57418 58673 57500 56939 56149 58000 55461 56844 54633 55400 54225 54783 55780 53668 53067 53040 53428 53008 52011 51559 51923 51768 51924 51486 50705 50799 51359 49478 49847 49293 49350 49103 49354 49271 48829 47560 47939 47851 47920 48588 49790 46495 50968 46443 46406 46312 45178 46133 45177 44998 46138 44659 45434 44065 44060 44480 43628 43569 44022 42946 42791 43032 42432 42525 42603 42969 41593 41514 41735 42055 40670 40858 41080 41744 40088 40020 39696 39329 39767 40458 39358 40898 38491 38456 38212 38337 39071 38910 38934 37624 38613 39571 36699 36412 44621 37092 38398 35807 37184 35895 35211 35312 39125 35056 35600 34476 34652 33983 34608 34943 33833 33599 32889 33838 33041 33344 32961 32800 35338 32154 33194 31725 32245 32231 31699 31393 31392 30826 32256 31162 30858 30820 30491 32031 29829 29677 29828 29563 30475 30935 29282 28988 28769 28852 28398 29220 27949 28594 28296 28290 28022 27342 27250 27337 27306 28072 27310 27137 26933 26775 26821 26394 26305 25922 25874 25567 25691 25747 25487 25419 25450 25261 25863 25166 25431 25026 24601 25661 25156 24606 24372 24451 24002 24337 23962 23659 23515 23879 23903 24654 23176 26466 23455 22656 22791 22668 22696 23974 23852 22710 22681 21647 21870 22613 22840 22442 21320 21727 22256 21780 21094 22742 21140 20731 20721 20477 20375 20153 20336 20150 20562 20465 20045 20247 20039 20130 19651 19927 19173 19190 19534 19338 19137 19118 18619 18453 18952 18755 18452 18454 17839 18504 17925 18044 19074 17963 18358 18055 17850 17825 17510 17633 17547 17512 17438 17263 16839 17116 16980 17351 16928 16300 16299 16382 16360 16891 16116 16470 16093 16246 15899 15794 15601 15609 16237 15643 15286 15696 15061 16090 15361 15412 15139 15227 16153 15598 15040 15310 15204 15413 14605 14589 14353 14726 14313 14240 14014 14280 14028 14206 13993 14027 14327 13966 14268 13357 13586 13595 13422 13385 13065 13318 13388 12949 13044 13067 13160 12677 12551 12696 12574 12567 12407 12677 12299 12210 12371 12499 12350 12255 12083 11796 12122 11800 11935 11781 11611 11557 11607 11717 11402 11651 11403 11522 11213 11209 11400 11052 11180 11166 11265 11169 10896 11018 10923 10633 10791 10785 10564 10771 10289 10239 10372 10201 10459 10217 10365 9878 10319 9911 10001 10090 9813 9871 10005 9723 9662 9776 9748 9742 9497 9643 9752 9551 9584 9389 9392 9315 9244 9134 9182 9110 9082 9136 8982 9054 8937 8759 8793 8809 8851 8589 8740 8663 8541 8618 8297 8360 8303 8116 8447 8280 8197 8062 8096 8018 7844 7948 8044 7943 8292 7957 7815 7934 7713 7694 7879 7571 7529 7614 7727 7648 7358 7481 7366 7466 7148 7282 7301 7448 7349 7090 7164 7079 7037 7075 7034 7015 6979 7005 6854 6952 6954 6891 6645 6703 6808 6649 6811 6721 6335 6786 6578 6427 6555 6414 6377 6381 6172 6420 6290 6227 6442 6338 6358 5963 6139 6179 5871 6030 6040 5998 5914 5892 5811 5914 5687 5699 5868 5589 5943 5734 5794 5606 5732 5642 5578 5391 5618 5468 5640 5396 5424 5473 5382 5357 5297 5231 5298 5186 5349 5206 5283 5195 5003 5211 5258 5110 5056 5105 5006 5094 5037 5060 5001 4886 4906 4844 4960 4838 4836 4861 4627 4615 4860 4703 4713 4679 4742 4528 4412 4545 4480 4611 4603 4420 4607 4375 4518 4332 4401 4459 4324 4300 4276 4206 4434 4292 4062 4457 4233 4169 4158 4121 4031 4242 3993 4259 4036 4165 3968 3914 4014 4040 3906 4081 3860 4099 3940 3825 3999 3846 3853 3712 3699 3832 3823 3832 3732 3690 3703 3866 3742 3583 3541 3435 3634 3539 3600 3686 3546 3567 3525 4008 3647 3388 3391 3343 3617 3372 3598 3256 3386 3281 3417 3617 3388 3140 3256 3210 3246 3079 3158 3018 3171 3395 3064 3803 3108 3062 3167 3120 2991 2885 3230 2975 3014 2820 2806 2947 2977 2959 2803 2990 3047 3039 2741 2924 2922 2869 2743 2809 2724 2636 2723 2714 2641 2691 2896 2849 2707 2801 2571 2680 2878 2508 2619 2589 2550 3084 2616 2578 2551 2535 2871 2701 2790 2648 2432 2716 2543 3546 2410 2399 2362 2454 2302 2796 2473 2473 2267 2324 2573 2612 2211 2395 2292 2351 2240 2332 2209 2237 2209 3097 2279 2277 2291 2194 2248 3087 2243 2053 2055 2063 2192 2436 2103 2135 2057 2151 2067 2023 2079 2106 2144 2075 2073 2040 2020 1995 1893 1901 1985 1969 2009 1929 1927 2000 2035 1920 1867 1782 1792 1882 1947 1935 1854 1852 1765 1772 1914 1845 1772 1802 1773 1784 1659 1707 1748 1655 1751 1674 1744 1806 1673 1797 1748 1667 1688 1614 1656 1702 1634 1577 1622 1628 1622 1668 1571 1562 1602 1614 1616 1490 1569 1632 1539 1558 1533 1479 1549 1506 1482 1487 1494 1469 1476 1516 1501 1461 1468 1331 1436 1469 1469 1366 1355 1449 1352 1331 1315 1402 1283 1354 1386 1288 1289 1253 1520 1259 1309 1288 1290 1289 1330 1217 1348 1605 1392 1287 1243 1342 1171 1147 1221 1164 1244 1190 1202 1204 1274 1123 1192 1180 1141 1184 1299 1182 1160 1125 1143 1112 1099 1179 1203 1160 1105 1121 1146 1066 1075 1077 1085 1050 1134 1083 1019 1036 1015 1085 990 1010 1078 1011 1052 1026 995 1010 1078 1019 977 1023 988 1039 1029 919 1017 982 937 963 991 973 924 963 985 914 896 864 923 843 921 859 930 886 946 941 923 920 866 917 895 913 906 899 942 941 879 855 819 846 790 845 849 709 832 800 848 810 784 836 788 856 820 791 814 833 768 805 756 729 777 752 831 717 708 714 749 789 736 713 755 667 737 747 777 778 705 675 707 694 688 708 707 691 691 705 689 625 647 622 678 755 642 711 610 689 625 688 641 691 684 670 653 651 621 653 642 659 645 635 563 619 643 664 667 635 545 570 586 627 588 566 627 552 564 693 508 603 532 590 612 576 570 629 573 579 515 562 638 579 522 587 557 553 544 504 504 531 538 530 462 560 487 506 476 524 479 489 502 474 493 505 440 484 485 545 480 480 493 447 463 482 454 466 484 417 523 444 465 432 405 471 493 436 462 407 412 416 419 496 419 398 445 436 384 450 474 445 406 371 406 374 443 383 461 411 458 390 386 426 344 424 417 420 396 393 406 432 406 414 355 383 385 365 403 390 374 382 367 391 365 375 363 349 413 367 339 399 340 383 319 355 340 313 349 317 334 307 314 317 346 386 312 343 320 303 327 317 348 337 322 303 278 301 318 348 291 311 316 314 270 307 324 302 301 255 274 296 296 288 272 275 304 292 293 279 301 265 280 271 288 253 247 315 255 253 268 255 245 226 250 256 270 215 255 224 252 252 223 262 268 263 256 219 243 248 230 243 187 235 188 219 238 204 258 219 256 215 265 217 203 207 235 240 207 218 241 218 210 210 236 221 217 198 173 200 199 205 206 189 216 220 178 199 197 190 202 201 211 163 189 208 193 216 195 200 205 199 220 201 199 171 161 179 176 191 194 187 180 173 186 176 176 168 170 160 184 161 177 156 186 206 154 180 147 166 165 154 177 179 179 168 164 162 149 163 181 176 177 166 155 166 164 144 159 151 148 156 152 150 118 146 133 164 145 149 136 141 147 140 121 136 138 137 151 120 126 143 118 139 114 144 134 127 134 127 129 146 117 97 127 131 125 130 103 137 118 123 115 107 105 132 129 118 114 129 121 112 113 129 125 99 126 135 127 106 101 114 120 132 104 104 127 113 104 112 109 161 122 122 108 107 100 132 116 99 129 111 102 104 112 102 132 107 115 100 101 123 83 95 79 94 102 91 83 111 90 107 91 100 130 87 106 94 91 92 94 90 91 92 96 80 76 72 107 90 101 90 98 79 99 77 91 82 110 97 75 98 82 98 79 79 80 65 71 70 83 94 67 82 76 80 80 83 77 95 76 97 90 61 64 78 85 89 64 65 72 71 74 66 74 55 57 77 52 78 87 69 94 86 58 65 76 71 83 82 88 66 61 52 65 59 70 72 67 
];
B = [
0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 527460 442984 84476
 546662 459876 86786
 551588 463986 87602
 513096 440063 73033
 682898 571999 110899
 529966 455611 74355
 550551 467126 83425
 1414598 1178507 236091
 536742 464233 72509
 670669 572945 97724
 1217597 1022594 195003
 661832 565813 96019
 1102763 932085 170678
 545736 472959 72777
 668900 572782 96118
 1137070 959205 177865
 667512 574516 92996
 1101500 932593 168907
 659187 568499 90688
 1050718 893160 157558
 660650 566791 93859
 1034140 879355 154785
 689174 593927 95247
 1034504 882363 152141
 673700 582955 90745
 1109376 941991 167385
 981767 841801 139966
 631983 550258 81725
 968804 831109 137695
 499749 440327 59422
 86376086 77911687 8464399
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
73 13 0 0
1 17 2 2
2 59 4 4
1 65 1 2
2 62 4 3
3 240 7 5
404 244 20 40
5663 413 57 59
85037 609 107 121
472563 943 201 242
1047628 1488 362 368
1819585 2070 652 700
2474319 3131 1548 1610
3048757 4781 4022 4052
3874399 7577 8761 8810
7796865 19710 19753 19646
7803197 35009 41772 41987
5916530 57505 66701 66641
3829044 92783 93028 93094
593065 134045 128655 128292
202167 175924 164272 163821
218935 212565 204386 205864
236707 270848 247454 247543
272007 312096 286778 287717
298771 357739 321418 323046
324172 388759 349022 351226
344177 405470 367415 370117
357681 406898 374640 375446
360348 392054 369300 371248
350863 368531 353296 356294
335091 337470 332318 333096
311353 308191 305840 308186
288430 284472 285224 286888
270576 267795 268102 269133
260845 255393 256732 257496
255534 250898 251154 252298
253519 247887 249838 250443
254266 249819 251082 252225
260183 254081 256525 257355
268849 264413 265045 266394
281826 274870 276157 277034
296508 289999 292506 293859
317027 310254 311551 311735
337426 328422 332077 333287
358705 349502 353616 355216
378877 372170 374637 374515
396655 390388 392619 393704
410387 404967 405408 407775
418016 413036 415805 415950
419365 414303 415522 417624
411015 407167 408261 409935
393641 390281 391490 393089
370552 368103 369084 369153
342801 341333 341786 342376
308410 308696 308556 309347
274285 275676 276145 276904
242841 243177 242355 243253
212434 212876 212096 212485
185506 185510 185429 186862
163991 163319 162725 163415
146491 146764 146673 145840
134718 135633 134814 134902
126115 126930 125407 126765
120987 120608 120277 120702
117020 117222 116450 117256
116910 117551 116865 117304
118464 118086 118644 118922
122531 122398 121817 122058
127231 127327 127094 126986
133567 134019 133556 134302
140151 139971 139360 139727
142831 143301 142178 144234
142094 141641 142328 142270
130774 129756 130528 130335
113908 113847 113315 113723
94156 94036 94460 94526
72513 72489 72107 72693
52211 51995 51942 52007
40543 40171 40594 40390
26989 27381 27306 27259
16273 16562 16401 16390
6921 6843 6838 6831
369 320 409 346
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
