A = [
788899 785202 4651687 714844 698954 666882 672268 663390 672014 658501 692446 783700 954585 1095877 1244928 1413222 1507425 1548952 1553774 1525506 1483445 1476193 1479894 1450541 1453997 1739418 1740301 1723378 1957391 1615202 1605154 1578641 1236944 1245657 1233719 1229210 1223598 1201395 1197064 1205991 1204057 1206814 1205606 1213909 1220395 1214307 1215194 1208991 1218486 1211812 1212815 1208391 1207893 1210776 1200410 1196569 1186987 1187272 1187519 1170390 1170795 1177009 1168651 1167726 1166049 1163598 1155234 1145934 1142372 1138105 1134417 1148343 1155448 1151151 1163667 1158897 1152944 1149549 1137739 1130872 1125516 1119737 1114017 1105739 1099475 1092715 1078978 1057081 1047267 1037917 1029508 1023233 1016055 1007239 1003478 995549 985796 979458 973831 965196 957746 950570 943994 937597 932565 926204 918337 913088 906807 898073 891527 884918 883581 878663 874008 872870 869282 895010 900555 898967 927832 937163 940147 937866 941312 938920 934654 930563 925070 919378 913050 907874 903250 900112 897788 894141 890142 885171 881766 873906 871161 866469 860401 857581 852975 848219 843675 840617 834469 833091 827701 821353 817729 811639 810699 805485 801639 797751 793136 789002 782818 779603 772495 768282 764947 760651 759338 753532 749789 746394 742947 737577 732565 728390 724245 720186 717083 714814 709817 706432 702593 698379 692982 690250 687948 685007 680158 677644 674314 670866 666984 663987 660342 656731 653629 648539 646162 642504 639587 637746 632233 629279 625549 620802 616009 613361 610857 608062 603420 599428 594777 589400 585410 581815 577505 574839 571116 567854 564455 561087 556717 553464 548358 543569 540317 536687 530900 525548 521059 514718 509343 505345 500600 495966 490304 488196 482415 480074 474964 468916 465592 462874 456876 452399 448408 444776 440723 437356 432361 428285 424578 420013 415871 412045 407325 403869 400425 396158 391256 387210 384134 380374 376262 371097 366988 363604 359217 356180 351862 348546 345198 341803 336865 333648 329851 326304 322173 320254 314468 312133 307110 305421 301268 297372 292575 289300 286007 283524 279033 276219 273078 269245 266985 263136 259038 256833 253101 249701 246268 243950 239076 236134 232989 230736 227122 224477 221110 219070 215691 213472 209736 207186 204337 201537 198229 194897 191910 189473 186626 183628 182149 179636 177485 173687 171038 169182 166878 164203 161532 158888 156764 155720 151500 149829 147681 145538 143182 140982 138665 137469 134665 132452 130975 129490 126946 124918 122924 121342 118921 117649 115889 113604 111885 110594 109363 106883 105146 104117 101788 100701 98103 96717 95826 93465 93169 91584 89821 88402 86641 85553 84192 83647 81773 80367 79000 77807 77045 75587 74561 72886 71787 71179 69365 68441 67582 66733 65438 64552 63578 62497 61093 60639 59896 58858 57754 57117 55419 54761 54039 53185 52789 51583 51126 49979 48872 48672 47446 47018 46104 45907 45139 44043 43426 42714 42228 41700 40948 40191 39757 39087 38966 38233 37295 37012 36361 35871 35319 34956 34080 33794 33277 32765 32075 31422 31286 30604 30277 29784 29498 29081 28303 27939 28066 27326 27052 26616 26360 25795 25317 25125 24739 24111 23888 23905 23305 22712 22487 22211 22307 21545 21347 21167 20474 20605 19986 19922 19398 19273 19072 18733 18447 18228 17955 17622 17464 17002 16706 16464 16446 16110 15866 15540 15621 15183 15035 14779 14555 14228 14138 13779 13997 13581 13367 13222 13037 12724 12616 12780 12424 12174 12155 11868 11542 11550 11377 10983 11092 10945 10675 10636 10340 10299 10046 9621 9787 9681 9518 9439 9221 9211 8848 8775 8778 8679 8499 8421 8286 8203 7911 7830 7746 7640 7349 7373 7408 7213 7174 7085 6774 6725 6891 6576 6529 6396 6366 6150 6021 6087 6075 5935 5747 5732 5597 5689 5439 5278 5231 5168 5117 5091 4971 4864 4925 4896 4718 4583 4571 4556 4363 4488 4387 4261 4133 4139 4103 3996 3949 3860 3857 3837 3740 3778 3577 3642 3593 3477 3315 3320 3368 3285 3324 3141 3022 2957 3055 2998 2876 2882 2921 2842 2825 2676 2717 2694 2551 2562 2465 2537 2396 2518 2435 2346 2350 2256 2280 2262 2239 2231 2125 2070 2049 2117 2006 1926 1923 1857 1938 1866 1804 1779 1773 1692 1741 1739 1660 1691 1673 1612 1552 1600 1497 1553 1441 1427 1508 1435 1455 1360 1389 1293 1343 1280 1332 1240 1250 1255 1204 1214 1159 1195 1148 1201 1122 1142 1042 1006 1083 1056 1008 1018 927 985 973 975 878 932 960 930 897 883 867 873 902 860 820 780 781 804 794 802 750 796 739 739 753 706 640 720 708 663 736 675 669 667 634 618 600 629 625 606 589 571 553 574 556 539 540 550 474 569 539 524 538 500 512 479 459 441 504 520 505 457 459 458 435 400 432 446 412 431 426 392 392 418 388 379 398 366 392 361 332 377 380 340 380 365 354 326 326 348 328 325 295 298 318 294 303 337 334 291 301 310 303 297 290 293 272 255 278 260 280 257 281 253 248 264 271 248 245 250 249 254 237 207 244 220 266 232 260 222 241 225 206 203 207 229 244 220 228 201 216 206 182 204 212 197 185 195 203 195 219 209 194 179 213 174 170 182 189 168 196 188 186 188 171 174 172 136 178 166 177 189 158 170 173 187 147 159 173 142 162 167 152 190 149 141 126 156 129 141 143 133 138 144 145 137 157 139 129 131 115 139 140 126 131 143 126 149 135 113 133 107 109 125 136 96 134 123 131 121 97 125 125 126 136 104 100 130 105 104 103 111 108 120 95 104 118 103 90 111 98 96 116 84 120 102 95 95 97 82 101 95 98 87 110 92 89 93 93 105 105 93 104 100 91 90 92 83 82 92 94 79 79 82 85 88 89 83 73 69 72 81 78 70 90 92 88 85 92 68 65 78 85 69 83 69 64 83 63 83 80 79 74 77 60 65 74 65 73 63 70 52 80 77 62 64 63 72 67 60 75 64 60 67 57 69 59 55 62 50 51 70 53 53 54 50 55 51 48 71 65 59 50 64 44 57 59 52 53 56 56 44 68 49 57 53 53 51 54 45 58 48 57 52 48 50 55 51 55 63 47 46 48 49 67 46 52 54 38 52 51 34 45 47 54 47 43 43 34 45 54 47 49 52 38 36 54 39 43 33 46 44 50 46 42 35 42 47 33 39 32 35 31 54 33 33 49 36 51 41 38 29 32 28 41 39 45 43 41 44 30 46 43 41 42 38 39 41 37 37 32 56 41 39 25 49 37 35 25 33 31 40 35 49 45 31 37 52 32 21 33 39 40 32 39 33 26 36 30 34 41 38 32 27 30 27 34 37 30 23 23 26 30 29 27 35 23 31 28 21 22 33 24 29 26 30 21 25 23 25 30 25 33 44 35 34 31 22 28 19 32 32 17 27 24 27 20 31 16 24 26 33 20 28 26 27 31 20 25 24 17 23 19 27 17 18 25 23 23 17 22 26 24 25 16 26 15 24 29 24 34 20 22 17 30 29 31 24 36 30 28 36 38 27 37 24 38 39 34 34 24 36 35 31 48 33 47 44 33 37 46 46 34 31 35 40 29 32 28 43 36 40 33 29 60 34 51 27 27 21 29 33 22 18 34 31 39 26 35 26 29 26 30 24 34 26 28 28 24 34 24 22 17 26 24 26 24 32 25 31 24 25 25 31 25 34 27 28 31 19 24 29 30 28 32 25 37 45 21 24 34 40 32 25 24 28 27 40 25 35 27 30 12 19 19 17 12 14 14 17 17 9 11 12 14 11 14 13 16 14 17 13 11 12 12 12 8 13 10 11 12 11 18 6 8 16 10 11 13 10 7 14 13 10 10 17 10 8 8 14 10 8 7 7 14 14 9 11 11 7 9 10 8 4 12 10 10 16 13 6 12 11 14 11 10 13 9 11 6 10 18 15 9 7 14 9 17 17 11 13 9 5 8 5 10 11 12 10 13 15 9 12 12 10 12 18 16 10 13 14 12 9 10 12 11 13 15 18 9 14 16 11 11 9 10 10 7 10 16 11 12 12 12 9 22 16 10 15 8 9 12 11 7 11 7 12 16 9 7 5 15 15 11 21 11 15 13 11 14 12 14 22 12 10 5 14 11 13 9 5 8 8 8 10 5 5 6 7 7 9 10 4 8 7 11 9 11 8 19 14 12 5 12 13 11 8 10 6 6 13 5 11 9 10 16 11 16 10 13 6 12 7 10 10 7 10 12 7 20 16 15 20 13 9 8 9 16 25 20 19 13 16 17 16 16 17 16 14 14 8 18 18 9 17 10 19 18 12 11 22 15 19 13 13 14 14 10 16 15 16 12 10 13 7 9 11 13 11 9 14 10 13 13 13 15 12 7 11 13 9 17 13 12 14 17 14 8 7 14 5 10 15 8 10 14 15 10 10 21 10 8 13 16 7 15 12 10 11 7 6 17 9 13 6 7 10 8 2 5 6 5 4 1 7 3 7 4 5 5 7 1 5 2 2 4 5 3 2 5 4 12 9 10 8 8 4 5 2 1 2 5 5 2 4 8 4 7 4 5 7 3 4 6 1 8 3 1 6 5 4 4 4 3 4 2 4 2 4 2 4 4 2 5 4 6 6 1 4 3 5 7 5 4 5 3 7 6 2 1 8 5 5 5 4 2 1 8 3 5 4 3 0 3 7 6 1 1 1 3 4 1 1 4 0 0 4 5 3 3 1 2 2 3 1 7 2 3 2 1 1 3 1 3 1 1 3 0 1 4 4 2 6 3 1 4 2 3 3 3 2 2 4 1 1 4 5 5 5 0 2 2 3 1 1 2 4 6 4 1 3 1 4 2 4 2 1 2 4 4 2 4 4 1 3 0 2 3 6 4 0 3 5 2 2 1 1 3 2 2 2 1 1 2 3 1 2 1 5 2 3 2 1 1 4 0 0 2 2 1 1 0 2 1 0 3 0 5 1 1 3 2 2 2 1 2 2 4 5 1 3 2 2 2 1 2 2 3 3 1 5 6 1 2 3 1 0 2 2 2 2 1 4 2 1 2 3 2 2 3 2 3 1 3 2 2 1 6 1 2 2 0 3 3 2 3 3 2 1 3 2 3 2 3 0 2 0 0 0 0 3 3 1 1 1 1 0 1 1 2 1 2 6 0 1 3 2 2 0 0 1 1 2 0 2 2 0 0 0 0 0 2 1 2 1 0 1 1 0 0 1 1 1 2 1 0 1 1 1 0 3 1 0 2 1 1 1 2 1 3 1 
];
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
 616459 515822 100637
 614019 513867 100152
 612771 513554 99217
 591164 495976 95188
 700436 588356 112080
 625009 524902 100107
 635814 532909 102905
 1217307 1026449 190858
 618744 520311 98433
 727750 612089 115661
 1131949 954488 177461
 717130 604565 112565
 1062534 896190 166344
 639342 539444 99898
 734268 619518 114750
 1100995 930524 170471
 747619 631559 116060
 1073909 906895 167014
 737870 623286 114584
 1057680 893526 164154
 743470 628743 114727
 1058729 895452 163277
 771245 652568 118677
 1051911 889308 162603
 751145 635508 115637
 1112106 941233 170873
 1003649 849432 154217
 722997 612439 110558
 1019255 863428 155827
 597305 505999 91306
 107908885 93713642 14195243
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
3 49 0 0
0 6 0 0
3 12 0 0
9 10 0 0
9 7 0 0
11 8 0 0
9 27 3 0
7 21 3 1
62 36 10 1
219 54 11 2
488 76 23 6
1288 82 61 24
4394 169 357 122
21951 266 1187 423
139955 504 1684 973
934954 993 2533 1901
3648070 2207 4512 4076
6194238 5329 10141 9776
4678437 10558 20182 20105
1908783 17894 32188 32184
752223 26906 44586 44553
238197 39355 56312 57054
97845 54854 69421 69993
90799 73230 84114 84645
104944 92902 101205 100941
124633 114418 120936 121022
146781 138362 142869 143525
172427 164571 168837 168845
200387 192788 196578 195796
229554 222329 225706 226396
261195 253724 256854 258120
291608 285596 287711 288278
322593 318332 319473 321806
352384 347105 349519 350208
379174 373253 375744 377284
404199 399940 400811 402071
423735 420581 422317 423140
442457 439965 440945 442621
460172 458302 457758 460610
476716 475829 476246 477297
495600 494733 491471 495157
514127 513433 511327 514667
536479 535609 534226 537173
560550 561239 559724 562248
590072 588929 589813 592000
620542 619186 618498 622336
653171 653038 650559 653674
683292 681899 679803 681728
707403 707892 707357 708640
728196 727203 727043 728362
736093 738589 734921 736973
731620 736511 731929 735067
715842 718608 715432 718904
690828 693472 689937 692383
652426 655976 653405 655908
605917 609068 606994 608543
557808 558831 557952 559480
507531 510606 507963 509899
461399 463582 462855 463618
421355 423516 421891 423832
393172 393301 393669 393699
371185 372608 371343 372833
354958 354423 353835 354480
352294 350643 351082 351459
359744 359607 358823 360021
377086 376609 376008 377304
401699 401392 401106 402169
436955 435091 434098 435019
472718 472344 470968 471783
495660 494874 493650 496791
500141 499175 499093 500616
486137 484913 485153 486068
443784 443791 442615 444226
370882 369221 368331 370159
296859 296465 295685 296771
226884 228000 226180 227189
165014 164733 164727 165096
113606 113752 113703 113889
84929 84998 85096 85109
61726 61360 60925 61590
42981 42867 42570 43242
27223 27412 27398 27591
2468 2426 2319 2329
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
