A = [
4065986 4688505 71523433 2124873 2230843 2133574 1921868 2109254 1904616 1731414 1725046 1656004 1647923 1617449 1578946 1568740 1555377 1550274 1547732 1507201 1499654 1508274 1476648 1461127 1453525 1592858 1594204 1596686 1712909 1592529 1612258 1602096 1472213 1479660 1485563 1487660 1477570 1464875 1471801 1471273 1458374 1468799 1462350 1455099 1465062 1447184 1435617 1461388 1442996 1432512 1443547 1410135 1422808 1413509 1390139 1384878 1377290 1385828 1359083 1347939 1358901 1345090 1334116 1328592 1316864 1317547 1303916 1291792 1289430 1283386 1281474 1281623 1273701 1272885 1275909 1266190 1262429 1259722 1246104 1234802 1229239 1224988 1208983 1199720 1200429 1181791 1163447 1141092 1127585 1121876 1109011 1097293 1093437 1081428 1073548 1067261 1060416 1050977 1039975 1032236 1026688 1017121 1011170 1004135 996985 988532 981291 973290 965940 956320 948720 945692 938042 932330 926924 919174 930685 926316 921386 933627 934087 929814 924728 921376 914534 908571 899069 894876 887950 880970 872975 866619 861068 854737 850178 841737 833614 828071 821307 813253 808095 799797 794410 787272 780600 775486 768296 761635 755701 748504 740910 734446 730531 721917 715589 710685 701914 695543 690430 683114 676933 673634 667198 659452 655246 648654 645121 637243 631966 626015 618970 617107 608795 606500 599421 595577 588445 583150 578903 573470 567899 562773 559132 553386 550023 544306 538544 534007 529221 528006 521023 516390 510993 506979 503572 496574 493699 488885 484602 479990 475368 472022 467489 463006 457587 453771 451022 445754 442699 438017 433558 429528 425837 419504 417744 413422 409803 406801 402463 399483 395164 392309 387601 384279 380042 375639 371730 369971 364189 359801 355999 353041 349380 344374 340552 337098 333956 330295 327510 324108 321351 316301 313238 311528 307683 304726 301676 298661 295808 291865 288833 285703 283185 281316 277915 273605 272332 268666 265241 263509 260276 257913 255420 251861 249735 246865 244363 240748 240036 236882 233956 231476 229111 226550 224676 221747 219556 217044 214472 212489 210235 207733 205573 204281 200868 198727 196421 195215 192683 190001 188322 186870 183837 182231 180977 178275 175797 174471 172384 170727 169409 166788 165387 163283 161552 159080 157301 156331 154685 152054 150765 149020 147721 145747 143925 142965 140977 139059 138149 136321 135110 132810 130814 130302 128695 127149 125804 123971 122758 120741 119297 118793 117537 115551 113895 113302 111341 110597 109992 108092 106597 105214 104661 103314 102427 100810 99287 98710 97889 95683 94901 93892 93140 91601 91088 89769 89190 87306 86263 85598 84556 83598 82781 81542 80965 79779 78915 77428 76744 75687 75218 74314 73218 72737 71445 70895 69573 69290 68297 67284 66544 65422 65031 64279 63384 62791 61645 61294 60584 59187 58907 57998 57971 57052 56305 55499 54910 54166 53202 52872 52414 51556 50936 50401 49537 49078 48512 47909 47357 46968 46035 45793 45564 44647 43770 43621 43094 42067 42302 40956 41104 40424 39948 39463 39139 38379 37829 37325 37094 36432 36248 35588 35354 34892 34643 33469 33841 33015 32846 32556 31603 31469 31191 30738 30364 30266 29418 29170 28635 28294 28099 27823 27519 27296 26875 26532 26230 26025 25560 25109 24961 24459 24440 23998 23389 23003 22857 22616 22556 22184 21804 21546 21230 21158 20584 20639 20304 20153 19708 19963 19114 18976 18621 18390 18384 17952 17974 17773 17472 17026 16918 17133 16732 16419 16246 15766 15675 15598 15456 15309 14933 14762 14596 14601 14135 13969 13922 13683 13207 13385 13238 12937 12698 12724 12363 12329 12489 11977 11820 11510 11659 11480 11322 11146 11017 10855 10751 10683 10429 10084 10234 10035 9694 9743 9745 9621 9350 9236 9037 9048 9035 8866 8750 8597 8490 8470 8246 8294 8079 7846 7996 7718 7743 7724 7597 7458 7451 7202 7295 7136 6857 6907 6801 6746 6512 6615 6440 6500 6235 6267 5990 5894 5859 5908 5678 5721 5748 5649 5510 5554 5362 5346 5255 5274 5157 4996 4991 5101 5004 4636 4723 4679 4802 4662 4618 4555 4562 4333 4346 4180 4213 4254 4241 4121 4007 4047 3979 3938 3888 3870 3852 3713 3717 3678 3570 3543 3509 3354 3455 3376 3508 3284 3197 3293 3200 3230 3146 3229 3115 3030 3011 3029 2893 2923 2868 2744 2788 2753 2770 2672 2613 2634 2629 2611 2491 2482 2591 2522 2454 2462 2337 2385 2398 2358 2287 2350 2318 2168 2237 2296 2138 2184 2140 2121 2086 2053 2062 2027 2012 1901 2044 1976 1910 1915 1862 1902 1834 1861 1867 1732 1824 1794 1731 1746 1762 1655 1728 1659 1665 1583 1649 1552 1557 1606 1614 1567 1488 1498 1518 1547 1433 1390 1491 1471 1510 1409 1346 1370 1357 1430 1308 1378 1359 1298 1246 1285 1248 1252 1277 1216 1186 1209 1234 1225 1180 1134 1236 1164 1183 1127 1204 1139 1046 1114 1157 1149 1085 1144 1103 1130 1056 1051 1098 1073 972 1029 1011 961 953 993 973 977 938 981 939 931 951 898 888 910 923 938 847 885 880 837 882 833 858 809 877 817 814 870 813 880 803 853 807 837 816 809 796 787 791 727 741 750 690 718 765 738 690 747 718 722 705 666 680 714 724 689 651 677 651 665 710 677 661 625 666 639 630 657 607 680 632 621 587 591 628 619 602 577 587 599 561 579 584 557 546 572 586 584 541 572 539 559 565 565 542 565 535 515 528 555 507 505 484 546 485 496 513 485 474 499 504 456 509 478 478 529 464 476 521 504 468 484 482 499 444 449 483 432 467 447 427 479 435 421 449 430 414 399 445 423 450 401 400 429 414 432 443 396 432 404 422 398 388 372 407 417 406 363 386 400 413 399 397 350 340 403 397 371 378 382 367 355 370 370 335 354 362 359 372 338 358 338 359 367 321 330 364 348 394 341 362 313 314 324 336 351 321 296 347 321 320 325 310 309 314 304 347 324 307 296 293 287 280 285 291 287 308 275 298 285 288 305 287 282 294 292 283 280 329 284 306 279 275 265 282 283 258 269 291 253 258 259 273 283 284 255 244 251 267 260 298 261 237 287 254 261 234 262 246 234 254 234 234 246 218 232 206 239 238 216 219 215 231 228 235 230 233 243 217 205 208 218 219 250 207 233 238 195 215 214 238 219 206 211 209 221 206 217 195 222 206 196 198 193 209 225 212 196 212 198 203 192 227 240 210 208 208 182 189 222 187 181 191 182 215 248 207 202 213 190 224 228 228 218 222 193 195 197 233 211 217 221 222 198 207 222 207 203 181 206 171 184 204 167 180 198 185 193 178 172 210 197 171 188 158 192 206 158 185 503 202 215 173 195 180 179 179 181 190 177 167 153 184 155 157 165 164 157 142 155 146 172 141 147 163 134 160 166 115 130 159 154 152 133 124 140 133 124 155 134 143 166 105 141 111 121 135 123 124 127 130 122 135 137 130 116 143 151 118 125 152 124 132 154 121 138 126 158 666 104 101 105 119 104 130 121 101 115 107 123 94 109 111 106 107 116 109 100 95 105 109 101 96 79 100 100 92 97 104 91 113 92 96 98 99 82 89 90 86 82 80 97 85 82 86 109 90 77 107 100 95 106 89 101 99 91 86 91 107 104 91 87 96 88 86 71 99 97 85 90 76 78 100 77 95 85 101 79 90 98 87 111 83 102 95 86 84 93 93 74 84 97 95 83 77 112 103 79 83 101 68 102 81 90 79 83 75 84 74 66 90 93 103 67 93 93 68 79 82 77 76 99 69 88 77 80 73 81 76 77 80 89 67 73 81 71 79 76 79 92 77 48 76 59 63 68 76 59 50 65 65 48 48 62 63 68 54 58 66 49 54 63 61 49 50 52 44 60 47 47 43 62 52 69 41 50 62 54 43 61 62 66 49 52 53 48 54 59 58 64 59 53 63 62 60 49 36 58 57 46 53 74 47 48 70 46 48 51 48 61 46 49 44 49 51 50 46 42 55 46 53 48 51 45 49 49 57 51 40 52 45 43 30 39 46 52 49 43 42 37 36 39 46 30 43 48 42 45 38 46 42 34 41 41 33 42 43 38 32 40 28 38 33 37 31 33 33 35 32 26 46 37 39 50 35 37 40 33 23 34 43 39 42 42 30 36 38 40 48 34 31 33 39 36 35 41 32 29 28 31 23 30 31 23 28 28 44 33 37 26 30 32 25 24 27 27 22 26 32 33 30 29 28 33 31 27 33 28 24 24 33 22 38 30 33 24 22 33 37 31 31 20 26 19 23 31 22 31 31 20 26 27 18 28 27 28 20 34 17 18 30 27 22 23 32 20 28 19 24 22 30 38 23 32 35 36 39 30 29 29 28 23 21 26 23 21 35 24 32 19 24 29 29 29 29 19 29 29 32 16 34 32 20 25 22 28 20 24 21 28 33 23 29 25 18 32 18 17 31 31 24 22 23 30 14 23 15 25 23 24 17 20 18 25 25 23 16 20 19 23 16 34 16 17 12 28 20 17 19 18 18 22 26 19 19 9 20 19 28 21 22 18 14 20 28 12 19 18 19 19 19 25 24 13 15 16 12 8 12 16 6 13 16 12 11 13 18 10 17 9 18 15 15 13 19 16 18 15 21 17 17 10 12 7 10 11 12 15 6 16 10 9 13 14 9 9 18 16 13 18 16 12 5 8 6 16 8 12 17 15 13 9 10 10 10 17 5 12 15 12 13 16 17 11 14 5 9 14 7 18 7 14 11 12 13 10 14 6 8 19 11 9 9 14 13 13 11 13 7 20 9 17 12 7 17 10 13 3 8 6 14 12 14 12 13 10 11 5 6 14 7 17 11 18 8 10 5 6 7 15 8 6 8 14 12 9 17 7 10 5 10 6 7 9 11 13 12 8 9 12 8 9 7 11 6 11 10 11 4 8 9 7 8 10 7 9 6 5 10 5 9 12 6 10 16 17 4 8 8 8 12 11 10 14 4 8 10 6 10 13 9 13 10 8 10 8 11 15 5 8 7 10 8 9 6 7 8 9 7 5 13 9 4 10 7 9 5 9 11 10 8 8 4 9 6 8 11 5 5 2 5 5 6 6 8 5 8 3 6 10 5 10 10 6 10 8 9 11 9 6 4 8 8 8 2 4 5 10 11 5 8 1 4 7 11 4 5 7 4 5 8 5 6 11 11 5 8 2 4 8 11 6 6 7 8 7 7 6 5 8 4 6 3 4 1 8 6 5 2 9 6 4 4 7 5 6 4 6 7 4 4 12 1 2 3 2 7 9 3 4 4 4 6 9 3 5 3 6 5 5 3 7 2 7 2 8 8 3 2 8 3 8 5 5 
];
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
 3182923 2738707 444216
 617450 530080 87370
 1083218 942264 140954
 2722076 2385003 337073
 1443341 1267174 176167
 1420265 1263899 156366
 3637359 3218329 419030
 2694380 2374776 319604
 1389024 1236770 152254
 4596680 4094870 501810
 2247349 1984380 262969
 961628 846276 115352
 5846557 5225829 620728
 1234749 1095116 139633
 797196 697849 99347
 9260356 8358194 902162
 1391931 1237483 154448
 1188797 1026802 161995
 14158837 12896585 1262252
 2550243 2281654 268589
 449061 386947 62114
 24184180 22084433 2099747
 2776803 2523001 253802
 580747 492752 87995
 392566 336829 55737
 3994952 3632751 362201
 464735 389971 74764
 388717 335935 52782
 472033 396279 75754
 357901 312358 45543
 91059567 84528251 6531316
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
345 1086 1 0
56 150 0 0
104 287 0 0
127 227 0 0
91 210 2 1
105 221 820 43
1774 301 2392 227
20629 300 3137 541
155013 374 4137 831
657744 428 5536 1391
1384742 453 6677 1815
2764300 641 8761 2913
4794899 911 12337 4706
7985686 1600 22140 9508
11879345 2593 25758 13388
16329508 4476 27563 16722
19743585 7601 30062 21687
21295493 12659 34357 29060
19182712 19788 41569 39488
13177931 28233 51455 51237
6328069 38050 62986 63381
1891869 50832 76044 76328
312729 66950 89650 90000
113923 85901 103845 105185
122973 106814 120288 122031
139538 128941 137748 139369
157327 150881 157197 159117
175634 173599 176884 178666
194922 194796 196908 199358
214418 214598 214792 218644
230597 233507 232539 235107
245190 248650 245996 249252
254625 259673 256649 260532
261477 269758 265536 268493
264884 274982 268746 272004
267811 274829 268977 272446
264386 272750 266599 269483
261330 267019 263461 265462
256396 262075 258665 261519
253729 258208 255180 257026
252665 255515 253654 255153
253694 255825 254043 256590
258870 259122 257710 260214
264407 266082 264546 267211
274176 274505 272609 275875
283879 283909 282046 285492
291966 294190 292043 294698
299728 300278 298727 301565
303452 304476 301686 304862
303771 303777 301237 305029
297411 298694 295852 298903
285441 289323 285792 288331
271607 274965 270551 274310
253696 257083 255444 257691
234385 238967 236025 236824
213831 216819 214694 216133
192891 196443 193157 195454
173532 177117 175045 176882
157953 159939 158082 158953
143469 144569 142564 144651
132338 134526 132311 133541
125507 126664 125948 125943
115334 115710 115733 116102
108753 109723 109078 110247
104367 104580 103756 104593
102938 102746 102538 103568
102528 102378 102064 102423
103657 103056 102735 103967
102906 102209 101905 103143
100625 101189 99587 101025
97250 96846 96838 97451
93734 93873 93761 94568
89795 90027 89413 90514
83394 83964 83841 84366
74992 75042 74390 75543
66562 66884 66839 67183
55759 55253 55279 55817
41251 41765 41463 41565
33613 33484 33529 33709
24926 24787 24484 24788
14728 14796 14681 14914
8301 8594 8461 8479
419 414 415 389
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
