A = [
7018840 7645914 139220386 3785323 2655975 2638421 2349604 2074351 1905040 1674382 1644723 1569891 1556849 1527534 1486858 1474954 1454121 1452232 1455943 1409907 1405560 1419367 1390072 1377599 1368922 1483303 1486375 1490036 1585797 1500003 1526777 1519262 1425893 1425647 1430613 1432918 1423073 1418084 1418471 1423573 1404765 1418835 1413934 1410696 1418615 1398500 1384407 1423002 1404843 1389462 1403909 1363943 1383136 1374952 1347195 1341219 1338178 1351504 1315046 1303388 1325323 1309228 1296413 1295167 1291768 1295130 1271441 1273206 1264152 1241500 1237451 1257305 1221905 1215819 1211370 1203956 1196743 1194703 1178145 1163386 1162086 1156329 1141204 1132244 1135437 1115125 1096044 1067071 1054282 1050566 1038844 1028282 1027968 1017822 1009358 1003323 995495 989803 981392 977111 971899 961976 958732 952500 946147 940819 932193 928423 921954 913921 907055 903741 900761 896092 891720 886325 911124 913900 910043 933892 936929 939404 937430 935029 928074 927163 918894 916783 905767 902116 893562 886077 884004 879976 872712 870016 859757 853837 850631 842924 835736 830622 824339 819729 812552 808187 799888 797611 786622 782590 775546 767451 762897 756568 750125 746593 739170 730506 724887 720743 711435 709719 700142 696332 689541 683451 681288 673227 666955 661620 654792 653542 644752 643663 634678 630134 626578 621012 616157 611260 603705 599652 594413 587654 586118 582186 576792 571303 564748 565401 556330 551126 544743 543713 538456 532155 526798 520366 519472 512422 509959 506497 502065 496292 491285 487426 480880 478506 473754 467467 462962 458665 452813 450437 446814 440492 437734 433714 430116 425541 419425 416526 411107 409354 400428 397580 392571 390013 383646 380136 373923 372967 369719 362464 358252 355068 349709 346701 342902 339077 338374 333287 329136 325548 321883 316801 313562 309714 309510 304729 300371 297010 294855 291017 286589 284305 279462 277283 272163 270246 268247 264042 260954 257656 255356 251801 250416 246738 245162 241690 239232 234915 233227 231144 226992 223735 222739 218947 217142 215361 212747 209987 207420 204617 202747 201303 197720 195313 192590 188587 187707 187427 183042 181326 178935 177065 173182 172316 170701 166408 165501 164160 162105 159549 156935 154995 154463 152030 150036 147750 146049 144596 142194 140545 138609 137643 135121 132544 131699 130672 128537 126731 125335 123299 121737 119481 119057 117570 116041 113450 112391 111548 110328 108955 108341 106089 104450 102896 101809 101410 100161 98448 97577 95874 95123 93860 91885 91659 90186 89033 87873 87119 85105 84367 83156 81512 81447 79467 79619 77592 76720 76505 75383 74113 72967 71550 71203 69830 69340 67808 67029 66366 65626 65576 63864 63683 61527 60795 60354 58998 58588 58165 57168 56506 55512 53605 53716 52871 53026 51040 50406 50155 49847 49561 47887 47099 46769 45510 45267 44974 45244 43901 43006 42246 41823 41088 40311 39694 40134 38629 38043 38574 37643 37135 36440 36139 35670 34401 35031 33432 33726 33176 32653 32332 32321 31108 31532 30565 30094 29528 29607 29024 28675 28390 27758 27124 27286 26092 26287 25633 25505 24893 24352 24652 27836 23939 23553 23291 22727 22625 22154 22034 21677 21613 21288 20877 19930 20422 19522 19678 19377 19166 19050 18635 18204 18240 17875 17317 17152 16712 16162 16661 16298 15837 15684 15757 15169 15269 15238 15151 14407 14420 14233 13972 14135 13481 13671 13372 12824 12684 12717 12628 12354 12190 11897 11694 11685 11582 11648 11547 10827 10886 10600 10584 10171 10575 10145 9842 9818 9770 9561 9510 9247 9157 9057 8939 8732 8680 8389 8309 8276 8316 8077 7995 7913 7797 7843 7438 7131 7171 7250 7200 6825 6804 6686 6532 6803 6510 6198 6333 6326 6233 6099 6072 5878 6039 5783 5777 5537 5385 5523 5279 5106 5406 5532 4903 5272 4872 4983 4914 4806 4616 4799 4682 4516 4576 4450 4388 4249 4289 4064 3864 4031 4179 3940 3963 3907 3797 3702 3896 3653 3501 3637 4160 3495 3376 3388 3312 3325 3147 3162 3131 3219 3102 3101 2968 2870 2890 3004 2700 2723 2757 2814 2885 2763 2671 2776 2662 2543 2624 2616 2537 2511 2493 2313 2412 2254 2329 2292 2284 2231 2209 2120 2161 2133 2154 2264 2181 2187 2021 1927 2167 1903 1903 1821 1754 1919 1848 1920 1795 1756 1801 1810 1704 1665 1714 1685 1599 1679 1656 1627 1672 1625 1553 1617 1613 1531 1371 1444 1613 1422 1422 1455 1467 1454 1345 1486 1408 1327 1303 1379 1377 1334 1425 1443 1286 1116 1208 1316 1190 1184 1200 1265 1060 1164 1153 1225 1163 1084 1159 1129 1087 1029 1112 1211 1055 1009 999 1039 1064 1015 921 1009 1085 1092 943 957 981 940 1025 933 958 922 894 960 870 786 884 880 815 860 833 786 849 914 770 871 838 863 850 865 805 807 838 949 849 809 901 821 810 826 806 738 780 783 785 772 709 711 802 745 797 711 793 740 687 689 685 654 702 678 685 633 696 656 620 627 627 586 580 660 640 640 586 569 693 576 625 579 645 605 549 569 596 578 580 501 575 524 593 617 510 515 589 572 560 510 445 550 562 496 538 469 499 629 791 662 509 546 573 526 476 524 517 506 566 495 491 491 472 487 525 468 548 572 552 500 423 462 474 480 459 473 468 440 419 400 511 403 418 446 413 406 439 383 438 447 406 451 374 407 402 402 412 409 401 422 381 376 352 402 378 368 426 439 367 345 389 385 438 353 351 352 359 376 329 327 388 352 351 307 385 311 330 328 353 334 342 309 334 288 342 357 297 324 333 330 372 302 308 296 345 299 355 313 385 374 320 338 247 282 348 371 325 342 279 261 298 312 306 286 305 261 312 297 288 298 289 290 300 291 253 356 301 372 260 299 322 258 288 279 317 233 243 268 278 279 319 261 271 291 283 292 260 287 292 295 291 278 239 257 257 265 267 247 259 254 224 250 252 255 275 233 252 266 223 223 231 240 225 244 242 188 237 277 240 263 271 305 283 265 255 222 368 263 230 271 231 244 297 267 220 261 265 228 265 272 237 266 263 223 218 280 248 229 257 247 249 247 263 244 245 260 285 241 221 262 273 264 265 244 230 277 254 257 271 244 281 254 262 224 206 224 288 240 262 242 245 276 203 222 252 371 253 258 257 243 282 322 260 233 259 297 245 237 304 218 520 246 259 235 224 466 206 178 183 204 217 231 182 199 210 192 189 213 198 240 223 225 207 265 203 226 215 171 177 171 183 211 169 197 189 172 183 198 181 232 218 204 212 177 243 216 208 205 1202 294 231 192 222 155 174 160 155 167 152 152 133 140 123 136 149 148 145 159 126 155 177 134 170 132 123 115 119 109 126 145 143 130 118 114 135 117 138 134 118 149 1407 139 159 161 190 215 198 231 229 243 166 175 145 162 116 195 147 113 134 168 171 162 131 85 125 102 122 226 106 137 99 109 125 120 135 134 119 123 99 134 142 149 146 138 186 126 139 116 89 335 148 126 111 120 305 83 139 135 99 512 114 115 116 108 116 87 74 91 65 161 101 109 121 114 775 96 87 107 95 117 141 101 104 118 238 107 72 104 107 91 97 96 93 105 94 100 99 107 95 71 82 115 76 105 123 106 89 102 99 91 104 91 108 89 108 74 89 91 74 80 78 100 85 75 111 102 91 72 101 91 80 95 108 77 83 88 95 95 75 103 87 107 64 109 79 59 119 68 75 84 101 81 81 87 94 84 59 63 129 98 96 96 88 1197 94 96 101 124 2668 164 106 113 114 2859 110 95 93 87 428 96 92 100 94 151 87 91 63 78 108 60 71 46 59 144 84 42 42 56 64 36 46 48 72 38 56 56 35 52 50 85 58 48 62 38 44 116 49 44 53 48 47 59 57 50 54 34 46 55 42 39 55 32 69 45 34 54 90 68 41 62 59 42 44 59 54 64 72 79 57 69 59 46 70 38 72 56 76 1363 107 90 52 68 61 75 53 61 49 64 29 45 34 62 36 45 61 58 39 57 51 40 22 46 53 50 37 35 54 18 68 55 31 37 57 39 58 34 49 46 34 45 38 48 44 38 46 26 49 45 41 35 53 61 39 35 49 33 44 87 28 37 35 29 53 40 58 55 40 40 53 32 29 53 28 65 72 38 33 36 45 34 40 40 45 46 35 35 52 36 56 28 43 43 59 37 57 41 34 40 47 46 33 63 106 147 146 108 152 84 108 132 129 238 137 119 134 159 154 116 155 144 340 213 173 132 144 109 142 200 46 42 51 39 55 52 48 39 40 51 77 52 45 36 58 51 75 58 57 66 52 48 46 67 31 65 57 34 37 82 29 83 58 63 33 61 49 65 55 42 34 35 44 44 49 48 43 28 45 37 28 37 34 30 30 21 44 35 30 41 27 24 18 25 29 22 35 28 27 32 30 24 34 32 25 34 25 31 29 36 48 30 31 28 19 32 22 32 38 30 25 36 9 33 28 28 15 26 34 22 31 50 20 29 36 28 17 37 25 20 36 40 43 26 18 32 29 28 28 32 26 28 24 27 34 20 16 34 22 34 29 44 26 35 16 23 24 10 13 21 21 10 12 16 9 24 14 43 18 16 27 16 23 21 15 17 24 20 24 13 26 21 31 10 11 27 58 9 15 21 15 22 26 18 36 13 26 16 26 19 13 29 28 31 23 23 7 10 29 9 16 18 26 18 19 108 7 8 6 21 23 7 8 18 10 23 12 18 15 11 37 14 20 19 8 21 14 13 11 19 6 6 12 28 9 17 11 15 15 14 16 10 14 19 19 14 11 8 17 14 9 11 7 15 99 27 15 14 4 12 12 5 9 9 17 13 12 9 17 17 23 12 12 12 21 14 20 10 28 13 11 13 9 13 28 29 39 7 23 10 6 7 3 8 17 23 16 10 11 15 26 13 28 11 8 5 13 14 5 17 18 7 9 28 13 11 9 14 15 12 20 18 22 17 18 16 13 18 9 16 16 13 17 16 24 17 14 1 27 25 25 14 30 28 35 48 50 66 29 27 48 15 25 50 50 43 31 38 56 58 62 38 42 64 43 50 45 53 41 50 31 44 62 65 44 45 65 38 51 40 40 37 42 25 43 82 33 54 48 65 48 57 69 54 51 58 50 51 65 58 57 14 38 75 67 33 30 53 72 40 46 26 51 73 24 25 21 8 19 13 15 15 10 8 8 17 23 17 7 11 6 13 19 6 5 11 4 7 10 7 7 8 9 8 9 12 8 13 4 11 1 7 17 10 10 5 16 10 21 4 11 2 20 5 11 
];
B = [
0 0 0
 932840 734526 198314
 1810805 1502069 308736
 1116282 926130 190152
 942232 795680 146552
 584936 487424 97512
 859022 752168 106854
 804938 708279 96659
 727147 640916 86231
 1235172 1090341 144831
 1552216 1415901 136315
 727790 640026 87764
 1532720 1390122 142598
 567253 503621 63632
 468253 414687 53566
 1227553 1132792 94761
 528797 468716 60081
 499252 443853 55399
 899913 824286 75627
 308369 266503 41866
 543008 490853 52155
 351662 305735 45927
 327659 285260 42399
 588179 525751 62428
 1290678 1186346 104332
 498651 445298 53353
 644040 577589 66451
 1410628 1297204 113424
 402896 350843 52053
 795635 716241 79394
 1856689 1711646 145043
 452725 401420 51305
 775004 705607 69397
 1524434 1420267 104167
 931315 851510 79805
 798990 740693 58297
 1962470 1841262 121208
 1545914 1404272 141642
 783039 724780 58259
 2544693 2400619 144074
 1459613 1328508 131105
 690927 626710 64217
 3452145 3255277 196868
 1042794 968400 74394
 604568 543908 60660
 5574631 5314339 260292
 1293787 1203979 89808
 881011 783423 97588
 8669563 8349124 320439
 2339165 2188779 150386
 444530 392262 52268
 14963133 14398072 565061
 3091135 2936958 154177
 617833 532094 85739
 399920 348744 51176
 4656958 4415950 241008
 499892 423896 75996
 405304 356687 48617
 510001 431752 78249
 364477 324839 39638
 155681552 149280319 6401233
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
205 616 0 2
60 91 0 0
83 181 1 0
104 141 0 0
76 157 0 0
74 156 260 18
808 344 843 102
13601 238 1115 228
178067 269 1337 263
1136640 419 1928 513
2671995 423 2355 757
5644763 578 3066 1041
10234922 851 5530 2099
17133039 1467 13917 5576
24527552 1996 15411 7948
31550095 3808 16387 10163
34297692 5130 18332 13926
31337560 8950 22731 20341
22766341 13964 29997 28988
12480390 20523 38531 38206
4697051 28573 47567 47520
1020463 37170 57034 57936
135806 48950 67311 67675
81818 63633 77940 78408
92161 80137 90035 90691
104447 96358 103249 104244
117278 112753 117643 118323
130703 131394 133394 133449
146498 146628 147149 148783
159525 162093 161732 164207
174615 176802 174141 175394
183300 191246 185032 185730
193127 199260 193216 197609
197234 206942 200157 201097
202986 211890 203596 203324
205957 209987 202293 202349
198303 225559 202077 205682
195340 199483 198155 196974
193562 197531 195428 195487
191222 192045 191386 192808
193416 193330 192279 189302
191811 190867 191674 190891
195493 203979 194352 194286
198756 199965 201442 199560
206160 206011 208138 207845
219213 213931 211806 213189
217491 217787 218043 216826
221155 222485 221522 221287
223702 223552 224585 223157
221743 223683 227129 222978
217355 218454 217077 218532
208163 209868 209498 209146
196276 199085 197841 198435
182891 185466 186401 189962
168329 171638 171059 169336
152531 155263 155573 154744
137823 140061 140074 140327
125367 127443 125798 125826
114331 115408 114983 114755
103333 103716 105984 104669
95992 98802 96232 95959
91221 92363 93127 91213
84808 88495 85947 84903
79768 80996 80650 80907
76320 76210 76971 76398
75652 75172 75929 76007
74685 74595 74767 74925
90345 104880 85837 78484
75196 74291 75520 74373
72812 73382 73103 73440
71015 70359 71940 70690
68172 68706 70446 70102
65690 66111 66128 66103
61155 60895 62429 60713
54748 54982 55463 55350
48657 48701 49467 48636
41231 40579 41072 40688
30584 30413 30314 30531
24168 24289 24526 24488
18389 18319 18379 18281
10752 10785 10928 10678
6655 6711 7074 6653
366 408 337 345
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
