A = [
1114048 1096848 5730203 967790 927814 876958 866021 848967 849566 850186 865012 893353 930424 973343 1025170 1081044 1139712 1202362 1268439 1329877 1391654 1450051 1511686 1556081 1610333 1808864 1851571 1885285 2059635 1926176 1977955 1999508 1851217 1893025 1874611 1872239 1856314 1805936 1784136 1750649 1721653 1697950 1666598 1645696 1627633 1605348 1595039 1579095 1566191 1561520 1548565 1536967 1528818 1519312 1509297 1500794 1492706 1484675 1475473 1462577 1455692 1446056 1445801 1434412 1426783 1426919 1418847 1501426 1498718 1489940 1572162 1567584 1557352 1547930 1532493 1520441 1507522 1494470 1482492 1469712 1453031 1443065 1428699 1414870 1400602 1386613 1373880 1360448 1345677 1332891 1319066 1307872 1292556 1278700 1264271 1251632 1235239 1223067 1209666 1194066 1177580 1168577 1154440 1136582 1127175 1111190 1099272 1087203 1074132 1061612 1047664 1035602 1020037 1009819 997873 984931 973382 961206 950756 939609 927003 915807 903838 893057 881091 870243 861718 847764 839613 830164 817988 807014 798744 787419 778130 768273 756695 747474 738348 727987 719858 710117 701308 692300 683073 675422 666137 656501 649209 639950 631253 623497 613858 605709 599030 592599 583850 577393 570094 561158 554047 546442 539307 532989 525709 518590 511582 505319 497857 491814 486298 478848 472635 465621 459756 454922 447041 442017 436626 431032 425230 419220 413173 408271 401911 398178 390935 387661 381345 377839 371787 367847 362426 356465 352226 348371 343593 338312 334999 329762 326099 320876 316753 313615 309057 305286 301043 297512 293226 290054 285908 282071 278747 274067 270355 266488 263771 259100 256400 253468 249918 246497 242838 239487 237372 232504 229924 226966 223649 222604 219103 215366 213071 210581 206425 204008 201606 199473 196579 194594 191329 188035 185969 183532 181219 178434 175849 174418 171533 169603 167323 164929 162543 160496 159126 156237 154690 152132 150176 148004 146164 144890 142192 140102 139090 136993 135248 134091 131405 129797 128626 126806 124480 123201 121881 120186 118551 116627 114010 113551 112260 110526 108931 107466 105895 105264 103616 101505 100270 99314 97706 97178 95933 93965 92962 91372 90541 88940 88292 87090 85477 84481 82924 82769 81784 80090 78912 78553 77196 75813 74998 74181 73551 71905 71283 70377 69108 69013 67143 66785 65836 65222 64166 63337 62717 61478 60884 60188 59109 58693 57773 56870 56288 55652 54669 53925 53488 52453 51841 51439 50976 49747 49412 48728 48197 47491 47142 46316 45660 44871 44488 43711 43254 42466 42689 41631 41587 40597 39791 39642 39160 38605 38122 37785 37078 36511 36207 35639 35248 35111 34421 34116 33254 32792 32933 32336 32137 31624 31100 30336 30603 30031 29537 29258 28702 28697 27772 27955 27189 27081 26644 26192 26206 25796 25509 25076 24597 24431 24360 24044 23787 23182 23142 22719 22527 22156 22268 21784 21672 21307 20902 20856 20477 20315 20099 19361 19663 19270 18973 18692 18669 18317 18154 17996 17826 17707 17446 17078 17207 16880 16679 16418 16056 15925 15818 15727 15540 15260 15224 15035 14761 14599 14486 14393 14238 14018 14031 13660 13853 13295 13496 13104 12731 12860 12971 12540 12368 12375 12300 12162 11902 11865 11593 11638 11463 11577 11101 10988 11011 10997 10669 10689 10690 10433 10342 10334 10016 9918 9968 9984 9702 9652 9725 9324 9405 9241 9164 9017 9043 8854 8991 8945 8757 8826 8613 8352 8363 8320 8126 8131 8107 7916 7829 7837 7698 7637 7440 7632 7367 7464 7310 7121 7182 7050 7022 6846 6956 6864 6856 6819 6700 6617 6495 6531 6485 6242 6338 6243 6291 6164 6056 6044 6075 6030 5895 5962 5822 5912 5780 5474 5780 5614 5545 5563 5387 5333 5322 5451 5294 5304 5122 5268 5204 5111 5150 5023 4902 4939 5014 4723 4734 4751 4722 4610 4891 4740 4690 4637 4525 4560 4491 4563 4484 4378 4387 4335 4402 4315 4315 4228 4139 4186 4130 4068 4070 4033 4003 4155 4047 3844 3939 3910 3777 3769 3848 3831 3847 3805 3761 3591 3648 3658 3567 3593 3528 3623 3481 3564 3464 3405 3479 3515 3341 3386 3314 3237 3409 3275 3182 3282 3226 3141 3187 3143 3114 3193 3183 3180 3166 3086 3136 2994 2974 3081 2901 2925 2930 2854 2913 2855 2741 2836 2781 2809 2813 2830 2852 2639 2701 2649 2701 2600 2719 2703 2655 2572 2750 2597 2695 2570 2508 2578 2575 2534 2477 2562 2458 2497 2553 2441 2453 2425 2402 2414 2230 2355 2371 2330 2352 2385 2257 2277 2321 2307 2283 2228 2299 2214 2189 2181 2223 2205 2128 2130 2066 2119 2147 2233 2105 2097 2118 2088 1996 2054 2025 2020 1959 2042 1996 1999 1974 1956 2002 1978 1896 1813 1922 1898 1853 1887 1953 1908 1890 1859 1829 1847 1856 1824 1733 1779 1806 1809 1712 1758 1704 1746 1704 1723 1754 1766 1676 1664 1783 1642 1721 1596 1659 1620 1586 1591 1608 1597 1583 1716 1607 1503 1548 1531 1537 1529 1490 1531 1479 1486 1550 1469 1492 1484 1460 1448 1421 1491 1444 1456 1391 1436 1398 1421 1431 1447 1420 1457 1323 1410 1343 1434 1358 1384 1390 1339 1417 1300 1290 1367 1286 1304 1308 1278 1302 1286 1204 1262 1316 1299 1284 1328 1217 1241 1227 1224 1184 1274 1266 1129 1256 1177 1186 1101 1201 1147 1121 1134 1191 1161 1137 1173 1181 1228 1140 1141 1144 1106 1130 1118 1152 1080 1087 1066 1052 1139 1109 1039 1117 1062 1034 1004 1078 1034 1048 1037 1022 1008 1069 966 1016 967 1042 1011 989 994 1038 999 922 957 933 1003 1017 975 958 994 1013 916 893 907 963 912 953 931 942 928 919 886 890 922 948 929 927 838 847 856 844 881 833 856 831 901 849 817 815 839 801 856 818 816 847 822 794 831 822 802 782 768 762 743 730 765 762 713 777 742 796 790 751 765 754 743 689 737 726 747 712 678 698 791 648 705 717 703 704 717 720 684 712 654 693 643 680 631 688 646 702 657 701 624 641 660 659 641 603 620 609 625 631 656 623 630 564 588 614 637 607 627 581 595 565 620 591 597 591 585 573 576 555 558 564 567 570 540 577 585 518 569 544 546 578 502 536 581 493 523 518 511 556 518 536 538 528 530 537 496 505 504 491 497 520 523 509 483 487 507 497 521 474 517 489 499 476 501 487 467 497 514 451 474 493 500 459 477 482 467 500 491 473 490 443 471 474 435 414 444 416 415 410 401 411 393 421 401 404 394 408 399 432 378 428 357 386 376 390 384 381 396 381 371 379 377 397 398 360 346 380 409 379 343 363 363 360 333 350 355 378 373 311 331 343 310 334 312 333 339 360 348 330 327 312 298 319 299 322 312 297 319 331 305 293 304 302 307 324 294 307 337 284 302 294 296 293 307 313 329 275 294 286 328 295 285 271 271 313 289 285 292 277 298 302 271 283 257 281 268 291 253 254 233 269 255 250 247 236 244 232 285 229 257 218 248 294 246 276 244 226 246 252 267 243 243 228 227 244 253 265 240 233 235 234 230 252 235 238 228 236 181 254 211 218 216 219 195 259 218 240 195 219 248 208 216 224 210 238 226 208 203 189 193 235 200 212 225 205 194 216 205 225 205 186 204 192 174 180 168 183 220 209 196 202 173 179 139 188 172 198 194 212 158 192 164 179 191 159 198 170 155 200 166 188 184 159 155 162 165 182 155 161 160 157 185 155 183 168 136 165 194 154 153 158 156 153 173 158 158 159 143 143 134 133 169 151 136 145 125 156 148 139 145 173 139 154 133 117 122 146 157 159 148 150 152 149 141 132 141 152 145 141 159 134 161 143 129 154 121 145 122 143 130 131 132 114 116 124 119 130 127 129 122 114 111 94 113 98 112 123 123 102 120 115 88 108 108 89 95 120 109 117 103 116 111 103 121 121 105 109 103 105 110 125 96 115 112 101 102 102 116 87 104 111 119 118 90 107 91 94 96 99 86 81 116 79 97 102 76 108 108 86 92 69 89 73 99 100 109 77 90 85 97 81 83 85 93 74 82 102 88 88 81 95 98 82 86 90 70 75 79 80 68 70 88 88 76 77 78 63 80 71 78 94 72 70 78 80 94 71 75 70 81 84 69 69 58 63 57 69 70 58 79 68 58 77 71 74 70 65 64 57 63 72 77 70 87 74 56 66 59 68 66 66 63 67 56 60 55 71 54 70 63 56 74 63 62 67 69 56 54 65 59 59 76 67 61 73 73 68 57 48 69 64 68 74 70 67 66 59 62 61 58 64 43 49 49 52 66 54 66 51 57 44 57 57 50 52 63 67 47 52 55 54 53 54 57 67 53 47 55 48 53 53 59 52 47 38 44 54 50 45 43 46 51 51 51 49 63 36 46 42 48 44 45 45 42 41 48 49 53 40 37 43 57 42 42 39 44 39 43 45 47 42 34 42 47 43 39 42 47 31 35 38 40 50 37 47 41 34 29 37 43 37 34 44 46 45 37 36 37 39 27 54 40 39 24 44 34 35 40 42 38 29 43 41 35 36 29 46 41 33 37 42 34 31 30 25 38 37 29 36 39 28 36 26 30 33 23 41 33 30 42 29 47 35 23 24 36 38 22 34 26 34 33 34 30 25 35 35 32 29 21 19 30 24 31 21 29 30 33 33 33 35 31 33 24 22 24 26 32 23 25 30 30 24 26 25 25 30 21 24 26 32 28 22 21 30 22 27 22 21 24 28 23 22 21 25 28 26 29 24 21 26 27 36 29 20 16 23 17 28 17 17 18 21 20 24 18 15 24 22 23 12 20 27 19 21 25 21 27 15 20 16 14 13 12 21 14 12 11 19 15 19 19 20 21 11 16 21 24 18 23 24 20 24 17 13 21 19 18 13 15 13 22 23 18 21 15 17 17 17 14 10 23 21 16 25 13 17 15 10 13 13 14 15 11 26 12 14 16 24 14 16 18 13 17 10 12 18 14 20 20 17 15 13 15 12 9 12 13 13 11 15 17 15 13 14 17 16 16 13 7 10 17 20 12 7 14 13 16 18 12 13 13 10 10 19 9 9 12 13 16 7 9 11 7 8 18 15 9 11 7 12 12 11 7 14 11 6 12 7 9 9 13 7 14 15 9 11 9 9 13 15 10 7 4 12 10 9 6 11 7 6 15 7 4 10 10 4 10 8 9 6 11 6 12 6 6 15 7 7 3 8 11 8 4 7 6 11 6 7 12 7 5 15 8 6 6 8 4 1 12 5 9 9 9 9 4 11 9 5 7 11 7 11 10 13 7 12 8 8 8 6 4 3 9 7 6 8 10 9 9 8 6 6 8 5 8 9 10 4 6 8 4 8 9 11 7 6 5 8 2 4 8 10 4 4 3 
];
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
 645461 470521 174940
 613933 448778 165155
 681975 499831 182144
 678176 497044 181132
 857460 628835 228625
 675857 497364 178493
 766582 563580 203002
 1558171 1145915 412256
 737427 544540 192887
 871985 644619 227366
 1408264 1039774 368490
 904079 668588 235491
 1340963 990987 349976
 758551 563080 195471
 918940 682153 236787
 1390698 1031786 358912
 907142 676149 230993
 1353451 1005516 347935
 949386 707852 241534
 1348020 1003513 344507
 905996 677511 228485
 1331494 993387 338107
 1020494 762556 257938
 1337967 1000976 336991
 939456 705706 233750
 1439283 1078809 360474
 1339826 1004661 335165
 934737 704452 230285
 1353687 1016519 337168
 829243 627009 202234
 92593516 72350290 20243226
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
168 313 141 4
25 60 2 2
23 80 3 3
15 115 7 6
17 100 129 61
31 133 9 6
219 165 38 25
1311 161 37 20
23208 219 85 31
212313 244 366 105
680049 280 2432 501
1585637 390 3680 1405
2867399 504 4794 2599
4032328 784 6668 4628
4366857 1456 9258 7395
4191094 2673 13643 11986
3493983 4607 18752 17839
2571106 7357 26026 25722
1632471 11931 35613 35320
811553 17895 47727 47770
305933 26255 61303 61127
117046 37737 76190 76224
95066 53935 92358 92511
108576 74676 110405 110501
127821 99729 130215 129896
150260 127966 153226 153376
174897 156964 177210 178696
199905 186580 204765 203958
225846 213782 229998 229806
249536 239714 253832 253018
269876 260086 273311 272841
286743 276347 287594 289837
300652 289122 299856 301047
304691 298490 309396 309083
310375 306037 315840 315956
313475 311762 319993 320200
318274 316771 322657 323102
323265 319998 328465 328929
326365 325953 332468 332714
333474 332299 338614 338543
340178 338749 345398 345701
348195 348119 354975 354416
359445 360935 364711 365790
372210 372111 376393 376831
385612 385951 389710 389734
400293 399198 404003 403357
413047 412293 414256 414036
421828 421511 424460 424462
427486 428156 429254 429952
430066 429104 430367 429892
425420 425168 427885 426958
416642 416422 417728 418086
403195 402887 402516 403785
383702 384516 385254 385108
362902 362489 362390 362080
339417 339442 337833 338454
313007 314135 312578 312791
287738 288431 287427 287292
262604 263836 262529 262310
240942 241724 240909 241447
222945 223628 223035 222362
209129 209105 208655 208995
200029 199773 200889 200226
192995 194048 192958 194121
195906 196154 196919 197536
207003 206407 206634 206560
222760 222839 222312 222832
242583 241265 241829 242812
270158 269625 269531 270252
303582 302388 302555 302619
343048 342485 342866 343592
364917 364672 365132 365741
387123 386583 386920 387000
399027 399324 397876 398960
391260 392297 391298 391606
351921 353358 352467 353357
294082 293344 293454 294001
207301 206150 205981 205991
108295 108959 109067 108217
40253 40071 39990 40237
6505 6669 6561 6568
54 47 48 56
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
