A = [
3419983 3227341 6256388 3567096 3425567 3306015 3140232 3388847 3290642 3330724 3587526 3846350 4425756 4945798 5333186 5780423 6290704 6993455 7235448 7126488 7549587 7796355 7708227 7752239 7907803 8962391 8910077 8844732 9507876 7825391 7911822 7692312 5965780 6071847 6078250 6030556 5949628 5837036 5792025 5786497 5741671 5729980 5784538 5836413 5786045 5702547 5626130 5633378 5461024 5414781 5438354 5258182 5347914 5358720 5269092 5230797 5186952 5202815 5029020 4886210 4936440 4812516 4792394 4794831 4724191 4750424 4665439 4587045 4539101 4433030 4381670 4342665 4267323 4266487 4253036 4216489 4177921 4151068 4071097 3980165 3904105 3848806 3782349 3724057 3710514 3638049 3570777 3457087 3386313 3337189 3282589 3215759 3190837 3136194 3100762 3085666 3044860 3024510 2990173 2940116 2895512 2850876 2807684 2780671 2741863 2717332 2688980 2663553 2632970 2607501 2561623 2535362 2496685 2473149 2454012 2436275 2810828 2829334 2814176 3184591 3190779 3171417 3141765 3110893 3076849 3040021 3007438 2986128 2959627 2929186 2888869 2840625 2798930 2783373 2714763 2698096 2672502 2634065 2611374 2591329 2557433 2526145 2494075 2442607 2410581 2370278 2354586 2337815 2296661 2324979 2243147 2222286 2193249 2149682 2118449 2088381 2059366 2036574 2016969 1988788 1973140 1936400 1908820 1896493 1860589 1836849 1830756 1790453 1764282 1749074 1718642 1699388 1690541 1660867 1634258 1611779 1592305 1568361 1548934 1521917 1510177 1494583 1472407 1453596 1443420 1417401 1391353 1375099 1359820 1413366 1338893 1313720 1297729 1286320 1266134 1249177 1232439 1214424 1194890 1180412 1171158 1156251 1138644 1135312 1123324 1106400 1084871 1068693 1053088 1044142 1020842 1007288 1003946 988362 976943 960909 948510 936506 920808 913722 896244 877137 865638 855866 840978 827609 817810 802967 791064 776880 763809 754849 739167 728078 720026 706977 698099 692013 679604 669447 664475 649249 642065 631136 624640 616849 604448 597553 589010 577541 574154 560905 554660 544267 535647 533212 522383 517870 507281 498358 491780 485253 476116 468928 463819 457699 450140 441907 436305 431776 424562 418794 413836 406699 398408 394817 389316 381568 377729 371988 367072 360741 355000 351688 345607 339808 336967 331643 328573 321053 318738 311169 309584 302158 298867 293834 290215 285460 280048 273375 270481 267989 263492 258254 254498 249872 246362 241488 239222 235921 232174 228860 225419 222665 218245 215082 213019 209214 203889 203031 198755 196225 193841 189942 189056 184782 182916 179608 177610 174982 170825 169261 164213 166181 162570 158551 156158 153600 151658 150388 148656 148163 143256 141223 138403 138359 135450 133866 130131 128995 126706 126635 125153 123273 119656 118026 116912 115507 113972 109879 110021 108091 106417 104796 103776 101996 99535 97328 97181 95365 93311 92026 89128 89148 87039 87587 83800 82594 81809 80389 78424 77259 75762 75253 73439 71760 71958 70021 68738 68675 66526 66147 64505 63982 62921 62506 60483 60300 58786 58627 57171 56309 55196 54557 53504 53557 52336 51191 50449 49240 48475 48752 47584 46954 46172 45059 44067 43758 43185 42917 41678 41486 40838 40104 39266 38540 38293 37925 37028 36155 36089 35467 34824 34185 33500 33197 33061 31870 31440 31208 30561 29696 29485 29228 28436 28266 27710 27335 26841 26561 25876 25338 25200 24554 24635 23897 23936 23337 23237 22462 22241 21747 21109 21210 20762 20147 20349 19774 19762 19372 19097 18532 18363 18195 17591 17452 17359 16786 16506 16812 16261 16125 15698 15370 15636 15333 14775 14490 14273 13668 13765 13578 13140 12843 13192 12712 12729 12574 12179 12080 11783 11597 11730 11320 11042 10646 10569 10728 10566 10049 10159 9955 9559 9564 9422 9311 9180 8849 8690 8875 8758 8552 8456 8399 8359 8000 7958 7683 7714 7330 7194 7383 7015 6993 7007 6757 6689 6463 6512 6694 6425 6115 6378 6071 5931 5868 5786 5779 5589 5274 5494 5217 5224 5392 4992 4928 4858 4820 4841 4711 4639 4607 4573 4574 4527 4206 4213 4211 4021 4222 4065 4027 3827 3840 3799 3648 3682 3636 3593 3697 3567 3510 3364 3335 3356 3193 3315 3126 3208 3142 3127 3020 2932 3045 2931 2894 2846 2676 2777 2771 2682 2701 2666 2444 2430 2397 2459 2229 2323 2387 2314 2293 2293 2207 2199 2244 2121 2083 2129 1997 2006 1939 1941 2026 1926 1898 1878 1933 1872 1724 1795 1778 1748 1811 1770 1728 1587 1625 1659 1624 1589 1569 1585 1559 1517 1444 1527 1413 1460 1508 1500 1475 1329 1356 1425 1473 1269 1262 1345 1405 1279 1225 1424 1266 1222 1295 1298 1200 1217 1103 1103 1248 1144 1117 1116 1074 1107 1086 1178 1097 1055 1107 1051 1110 1019 1033 1019 986 1010 949 1033 1036 946 994 967 901 929 933 937 980 928 927 882 863 963 844 844 817 869 848 844 814 802 798 795 847 802 790 828 844 728 797 791 773 782 775 732 764 755 701 741 767 800 686 739 702 713 666 689 676 660 703 713 623 635 653 642 613 658 688 706 647 627 587 612 590 596 559 630 598 655 624 561 647 590 565 615 543 530 523 547 486 553 519 527 553 514 507 583 535 484 532 512 579 479 514 444 519 416 503 545 515 468 470 520 459 481 463 498 430 489 459 436 454 507 460 461 448 501 502 475 417 480 411 419 402 446 429 460 430 392 418 442 357 435 409 437 376 405 417 431 500 424 401 421 419 481 430 450 362 406 369 365 361 396 397 361 370 424 393 352 380 380 411 414 357 426 342 320 387 344 413 380 365 363 338 423 353 369 333 292 344 337 347 360 289 339 329 333 323 335 302 393 324 261 330 303 381 298 313 312 333 350 303 304 282 295 297 292 263 275 266 270 304 319 284 304 272 285 282 219 284 289 278 298 292 332 231 299 263 299 285 273 271 266 235 268 223 274 254 304 237 277 252 238 215 250 236 248 213 266 242 232 224 247 215 175 211 233 237 245 244 245 243 277 285 212 209 236 215 204 243 201 212 175 198 264 244 190 190 204 223 201 204 225 172 205 193 208 186 239 204 199 227 220 213 223 157 189 209 174 236 197 215 195 209 219 202 171 188 209 191 187 181 197 202 178 192 202 181 159 202 206 154 180 168 171 183 193 197 188 147 175 167 192 174 166 204 136 214 156 155 157 184 193 195 180 175 150 200 182 151 152 150 180 172 169 146 173 174 157 153 200 184 172 189 174 229 209 190 198 207 219 216 198 209 211 214 219 215 180 183 169 177 177 195 191 193 200 217 192 208 180 166 212 181 203 170 199 181 186 193 172 128 156 143 180 148 181 163 188 226 198 177 208 277 181 227 244 220 211 232 233 216 242 1880 348 328 278 244 166 184 199 151 156 136 170 141 150 142 157 155 178 137 139 138 168 161 166 155 135 145 132 119 138 114 169 127 98 124 114 152 135 105 103 125 109 120 120 163 117 181 269 242 206 197 240 132 137 126 123 128 107 128 117 125 122 107 128 117 89 78 101 126 303 165 118 78 110 74 110 97 98 107 114 91 91 111 84 107 81 88 80 120 85 109 96 75 111 80 83 95 110 88 90 106 111 106 86 98 87 90 97 87 103 85 89 78 81 98 82 98 94 130 98 101 86 109 78 62 84 114 79 93 108 114 127 108 127 106 106 99 93 100 94 130 113 121 128 126 133 127 134 130 138 145 148 119 155 153 169 163 172 151 116 161 161 142 130 138 146 144 125 163 146 129 169 165 139 155 192 190 133 154 168 156 182 161 181 158 159 197 231 164 187 212 210 214 215 218 202 206 192 199 177 214 195 188 157 181 192 218 184 218 172 157 158 95 93 90 87 101 98 91 92 92 77 76 105 56 72 75 64 68 63 97 63 68 47 79 49 77 73 51 73 65 51 65 39 53 65 78 59 43 56 57 41 62 57 37 52 48 45 48 60 38 42 63 52 43 35 50 46 35 44 52 54 44 41 37 51 45 48 36 47 48 46 58 49 53 54 40 61 47 48 48 39 47 56 46 42 46 53 42 55 45 29 41 71 75 74 47 58 58 49 35 36 62 62 62 47 48 37 42 49 53 60 40 35 50 57 56 41 24 38 59 42 37 41 44 43 48 41 47 60 72 25 56 51 62 56 66 40 69 43 58 56 44 52 59 44 51 43 53 72 45 70 43 50 39 40 48 30 51 46 48 34 46 74 35 82 53 46 33 54 46 48 37 39 60 39 48 46 37 37 38 57 62 49 48 48 46 51 50 50 81 31 32 47 55 49 47 36 41 52 47 45 30 40 49 55 58 56 28 31 29 37 38 44 27 30 53 64 64 39 61 27 40 54 41 71 72 40 57 77 65 74 46 80 60 85 73 64 80 82 73 69 71 77 100 97 64 70 77 80 64 89 57 59 72 93 61 58 77 76 115 45 48 66 59 81 41 47 33 43 44 45 51 29 38 52 47 36 48 27 23 34 44 28 24 22 32 29 29 45 24 32 31 39 29 39 18 25 19 31 30 19 30 23 38 29 21 24 38 33 18 38 32 23 36 19 22 47 25 20 15 20 32 18 40 29 14 25 29 17 30 19 36 22 29 15 17 15 12 22 16 36 21 23 20 31 16 19 20 24 22 18 10 22 34 11 22 14 20 31 10 12 8 18 19 21 17 18 20 17 23 12 16 12 13 17 23 25 16 15 28 10 11 10 16 17 16 20 26 22 22 16 14 22 15 17 10 18 15 21 11 20 18 9 25 23 37 10 11 15 16 12 18 14 8 12 4 13 7 14 13 8 10 22 10 16 10 8 11 11 8 10 12 15 12 17 6 5 15 12 11 6 12 17 4 13 10 20 7 7 10 10 17 10 11 7 8 0 13 17 14 9 7 18 7 20 15 7 9 7 8 13 12 15 11 7 4 10 7 12 9 12 8 14 8 12 19 6 3 13 9 19 9 14 12 19 7 12 7 9 12 14 10 8 19 15 10 8 13 9 10 15 2 8 7 5 7 8 8 6 6 11 10 9 7 18 11 6 7 9 10 16 12 8 11 14 6 5 22 9 3 10 6 12 13 13 14 4 6 16 31 6 14 22 10 14 9 10 13 6 5 7 3 25 11 11 10 15 7 4 7 12 9 20 13 4 8 10 16 8 13 19 15 8 14 7 5 4 10 10 12 10 10 12 5 8 15 13 13 16 8 7 10 17 18 7 9 9 9 5 7 13 14 6 11 7 9 14 20 10 19 6 17 13 19 19 9 2 17 14 6 7 7 7 4 8 8 12 11 6 10 5 10 9 7 3 7 13 13 7 3 4 7 2 7 9 7 4 4 1 5 11 16 19 5 10 8 10 6 6 6 3 3 5 5 
];
B = [
0 0 0
 1098402 807209 291193
 2898322 2241262 657060
 1773137 1403141 369996
 1470476 1147645 322831
 1306689 1027579 279110
 1044942 822941 222001
 946427 746410 200017
 966034 771069 194965
 1068175 851320 216855
 2090028 1746453 343575
 1301279 1083643 217636
 1182512 979912 202600
 1036208 848191 188017
 988647 811477 177170
 1526217 1282790 243427
 1186504 985348 201156
 1275854 1076656 199198
 1030173 856672 173501
 1087567 898581 188986
 1416397 1190001 226396
 1206007 1003775 202232
 1250399 1052117 198282
 1265661 1061710 203951
 1172938 977512 195426
 1423057 1193045 230012
 1247326 1043144 204182
 1349790 1123228 226562
 1206268 1016168 190100
 1352316 1134362 217954
 1367158 1151790 215368
 1334152 1119976 214176
 1344896 1129366 215530
 1274825 1075958 198867
 1600369 1338149 262220
 1349850 1143447 206403
 1353403 1135801 217602
 3204042 2643688 560354
 1309311 1109862 199449
 1606499 1354985 251514
 2883405 2399146 484259
 1589658 1340920 248738
 2579180 2144729 434451
 1385907 1178536 207371
 1602065 1353751 248314
 2685685 2243455 442230
 1660485 1405167 255318
 2671745 2229583 442162
 1595252 1352752 242500
 2765941 2322980 442961
 1703580 1451509 252071
 2721649 2285975 435674
 1915448 1634866 280582
 2898547 2446403 452144
 1602238 1360354 241884
 3083142 2608570 474572
 2424755 2033624 391131
 1511984 1288669 223315
 2420779 2031402 389377
 1131291 977313 153978
 306772970 278271102 28501868
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
72 125 1 0
26 20 3 0
48 21 1 4
54 40 1 10
64 62 0 1
84 63 8 1
171 123 14 1
381 139 35 7
174640 219 44 16
1644623 261 60 32
3456727 371 90 57
6983732 469 161 122
12239445 602 1189 456
20098660 1188 4918 2509
26730672 2004 8215 5999
31017318 6721 17597 15815
29014175 12317 44230 42870
21544677 26290 81631 83352
13972175 46130 125209 129957
7320923 73148 185805 192328
2848441 105444 239409 241815
877510 147950 295048 295742
422981 220218 341648 345301
407929 283485 384676 398792
417229 384844 438784 455982
489205 471567 509632 508209
523872 613115 576628 569115
604141 690520 656387 660267
690048 791898 739866 750137
779342 899358 809794 865554
814829 994572 873024 877048
854322 1012612 925865 946273
923844 1104771 985496 1022051
919786 1092826 982261 983051
919881 1089294 1005974 1009962
929314 1085675 976594 975371
853760 967916 937450 921263
844421 934148 882055 886092
845427 915233 876567 879500
843683 905036 872117 876979
846838 895881 867901 870327
855762 894226 870393 872810
868178 900165 883319 885777
888707 912015 901708 902678
918911 940353 928693 934545
965264 975903 966150 971021
1013880 1028009 1018492 1026661
1070535 1080902 1074205 1079505
1128814 1141612 1135636 1137825
1195553 1205362 1196209 1201887
1256244 1262707 1255085 1262046
1298697 1309410 1299588 1307851
1327157 1333161 1324586 1334655
1333708 1345451 1339597 1342127
1322474 1332919 1325442 1331494
1282032 1291564 1283945 1289910
1223569 1228478 1220662 1229041
1144148 1148497 1139875 1143176
1047596 1052178 1044163 1051573
945407 947847 948937 951865
851707 857258 852878 855374
765944 766007 762836 768299
677321 680472 676474 681427
600667 605491 602772 605463
552484 553418 552629 553831
525198 528736 527573 529791
524069 523158 522587 523280
499382 502335 497974 500900
477527 478170 475962 477849
477830 477632 474221 479562
460376 462229 461783 464138
439365 440102 439264 444254
401618 403096 401298 404465
354802 355107 353064 354384
303442 304919 302654 305324
250794 250706 248848 250726
180882 182204 182113 182838
127631 127648 127525 128609
99381 99244 99009 100109
68370 67546 67720 68164
35733 36159 36119 36127
16505 16495 16040 16722
921 965 850 885
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
