A = [
1349118 1215343 3268823 1270656 1210835 1128366 1104316 1138944 1223572 1194865 1369314 1328473 1465005 1697805 1901916 2190860 2339793 2476139 2476146 2430205 2216569 1980282 1858966 1810965 1817014 2152341 2180385 2178568 2358143 2010538 1996730 1906325 1577280 1603434 1566498 1586672 1579081 1469754 1480666 1459138 1425898 1443002 1446330 1497254 1549185 1524587 1540473 1532692 1531874 1535729 1477391 1480564 1528997 1526206 1522143 1548876 1532541 1536763 1501679 1455237 1434477 1428852 1434182 1440502 1472305 1517145 1512908 1504953 1500946 1480564 1463816 1466574 1487890 1491160 1506371 1531105 1541926 1518235 1507817 1482059 1457341 1444867 1422099 1425757 1432504 1428109 1415748 1393072 1381133 1363514 1345540 1333459 1330842 1321003 1321548 1324051 1314561 1313873 1310346 1282897 1268705 1266568 1248818 1240791 1243751 1244826 1243926 1241110 1234667 1226053 1210038 1198458 1190811 1184767 1181711 1181679 1189372 1185695 1180827 1170160 1161900 1149694 1141030 1132142 1130634 1127742 1121451 1120829 1115570 1109783 1099620 1090825 1082813 1075388 1068193 1063282 1054433 1051509 1048351 1041261 1035956 1027595 1020930 1011075 1003964 999105 998876 996827 997185 996035 990906 982442 976268 966299 954963 946858 945115 939478 935359 930434 921551 917696 908868 901596 897992 893607 887063 884281 879649 877272 870451 867716 861635 857047 849033 844237 839838 834802 830508 826449 824877 818858 814945 812917 805061 800099 793863 790029 785745 784560 783154 777496 776621 772620 767488 763789 761388 757554 755648 753166 748029 746169 742509 737990 735325 726824 724351 722800 717414 711928 710149 702647 694721 691139 685823 680833 674395 670225 671028 665615 664714 662037 657188 659130 651489 646024 639904 634045 628238 622159 617167 613167 610128 605279 597940 595868 591476 587375 582368 576647 573976 570747 566148 562078 559278 557253 552158 548147 544149 539515 534470 530345 527807 526485 522419 518626 514559 510876 506297 502115 498015 495394 490692 487367 484875 481553 476939 473545 471322 466519 461880 459401 455106 452044 449029 446331 443444 439355 435247 432002 427666 424274 419617 417351 415181 412600 408638 404788 401537 398735 394916 391112 387774 384422 381567 378417 375212 372126 368296 365377 360609 357275 354180 350185 347176 344705 340671 338514 334406 332651 328648 324657 320458 318037 313975 310986 307484 304667 302680 299541 295263 292081 288054 284783 281647 278572 275262 272855 269218 265963 263550 260101 257161 252768 249569 246187 242964 239843 236435 235014 230429 228427 225316 221947 218484 215397 212398 209631 206960 203663 201574 197994 195309 192399 188525 186460 183251 180587 177219 174644 171875 169028 166195 163591 160780 158633 155570 152417 150621 148021 145698 142267 139540 137138 135220 132063 129666 127462 124501 122626 120442 118167 116079 114101 112041 109307 107409 105134 102665 100527 98973 96940 94629 93327 91099 88672 87322 85368 83760 81456 79853 78578 76773 75162 73196 71824 69911 68529 66873 65145 64225 62561 60824 59400 58218 56866 55180 54204 52805 51581 50297 49324 48075 46745 45638 44872 43144 42479 41076 40314 39357 38621 37109 36621 35713 34620 33552 32932 32046 30919 30139 29692 29095 27966 26848 26441 26064 25330 24623 23991 23282 22877 22221 21357 21032 20388 19993 19199 18785 18299 17530 17422 16731 16177 15761 15394 14893 14521 14081 13486 13343 13014 12686 12211 11664 11573 11551 11135 10627 10437 10259 9868 9445 9130 8772 8690 8563 8140 8134 7881 7505 7294 7085 6903 6755 6556 6245 6296 5959 5945 5695 5524 5445 5229 5165 4969 4744 4820 4518 4531 4336 4290 4117 3990 3824 3731 3688 3540 3324 3383 3271 3265 3198 2979 2863 2817 2728 2737 2644 2488 2547 2483 2323 2441 2335 2261 2204 2155 2006 1955 1936 1906 1878 1818 1797 1748 1709 1613 1592 1554 1542 1475 1468 1477 1387 1359 1432 1362 1295 1230 1223 1213 1172 1166 1176 1124 1130 1043 1077 991 945 987 977 947 971 913 940 913 871 852 813 832 873 806 761 748 743 770 699 750 755 676 694 702 677 619 604 604 629 604 600 598 586 538 563 525 563 526 544 562 534 512 556 534 526 482 488 532 502 509 501 481 479 514 439 445 469 492 450 436 437 440 420 439 429 399 425 422 398 384 396 381 393 381 343 388 392 373 342 342 371 380 370 336 324 382 371 326 345 384 351 358 327 375 318 348 374 333 331 360 342 324 363 320 316 337 306 323 330 328 321 274 282 295 302 332 280 285 314 300 268 313 301 306 304 273 307 258 271 284 288 273 274 278 273 277 258 267 264 273 273 274 246 254 268 253 269 262 275 270 268 252 238 215 245 239 255 232 212 277 211 242 221 255 249 269 229 247 245 249 221 218 259 234 219 235 222 214 223 233 238 206 232 220 219 234 189 235 202 204 213 207 209 200 219 198 210 186 220 204 205 178 198 198 181 200 175 188 182 165 194 197 201 198 212 180 182 178 190 181 184 171 172 148 183 187 181 159 197 155 179 185 178 198 162 174 171 186 189 161 155 167 176 143 146 163 158 170 173 161 159 176 158 170 152 184 167 155 151 158 159 139 160 150 140 149 152 131 147 138 134 129 141 120 129 141 141 131 145 154 126 146 137 106 134 156 125 141 127 142 130 124 130 144 120 123 129 145 113 122 132 153 128 124 125 108 124 107 116 105 106 115 113 109 113 121 110 110 101 92 128 105 127 128 109 113 118 124 110 106 109 105 91 94 114 86 100 81 111 88 104 92 95 116 84 89 107 96 99 87 106 99 103 94 96 108 82 116 100 100 118 87 81 82 86 101 95 98 94 94 92 89 90 81 89 84 76 83 86 78 87 85 88 78 86 87 91 96 98 71 79 79 80 72 68 76 83 96 62 88 81 85 74 74 77 76 75 66 78 81 79 83 62 71 93 73 66 55 85 73 67 55 89 61 84 61 61 66 79 74 70 75 79 64 59 75 64 75 70 75 59 58 63 64 59 60 69 57 62 62 68 62 60 50 56 59 50 49 52 57 56 55 55 54 70 67 51 50 69 64 57 58 55 59 65 67 53 53 52 40 62 66 53 59 53 67 56 48 47 55 48 50 47 54 54 65 39 56 44 47 57 61 49 55 45 40 44 47 52 47 43 48 39 30 43 46 66 46 54 44 49 44 41 50 46 47 43 56 52 44 44 54 42 52 47 45 41 57 26 49 44 39 38 60 50 39 39 42 40 43 44 46 44 48 41 42 48 44 38 40 39 44 39 35 36 39 32 46 34 35 28 43 37 42 48 34 39 33 36 30 23 38 35 42 38 36 42 36 40 44 32 35 37 39 39 39 35 47 43 25 33 55 38 38 35 41 28 36 32 31 45 39 29 31 30 47 38 23 36 39 30 37 22 35 22 30 28 33 33 30 17 24 27 27 23 27 30 34 30 23 27 24 32 26 37 24 31 22 22 20 26 12 16 24 26 22 16 23 19 27 19 25 31 21 16 23 42 27 19 24 24 26 22 15 32 20 19 22 21 24 21 24 29 24 17 25 24 31 27 19 21 18 22 29 29 16 31 39 17 29 29 34 26 29 23 25 41 42 20 34 20 27 21 30 32 23 39 29 21 30 18 33 30 34 20 21 37 29 18 18 15 16 15 26 15 17 25 13 20 18 18 19 11 13 15 19 13 22 19 21 19 13 16 17 19 15 15 16 14 10 10 17 10 15 18 18 12 18 9 12 17 11 17 13 14 10 11 8 23 13 17 12 15 7 12 8 11 10 11 10 10 6 9 14 7 17 11 12 16 10 17 5 22 8 13 12 15 17 14 16 12 11 13 19 16 12 14 19 17 11 7 15 12 11 9 10 10 8 8 11 15 19 3 11 9 8 10 10 7 13 14 14 11 18 17 9 9 8 10 11 10 11 14 7 7 11 14 12 12 10 8 13 2 10 6 8 12 10 9 14 11 20 6 14 16 13 12 9 16 25 15 15 20 43 18 10 7 22 30 20 11 14 14 24 22 17 20 20 15 7 12 13 27 50 15 15 8 10 19 26 21 27 15 61 35 15 10 20 31 13 18 15 16 52 67 8 22 25 22 19 15 10 7 10 7 5 4 4 9 5 11 11 7 9 8 6 6 7 11 9 6 7 13 6 6 9 6 14 7 7 5 6 4 5 10 10 12 14 8 9 17 7 11 23 18 37 17 10 17 32 40 21 20 5 9 15 10 16 8 44 23 11 15 12 13 33 6 8 5 8 10 22 12 11 36 8 12 10 8 18 26 10 14 10 9 14 6 13 14 55 30 11 21 8 8 10 10 7 11 8 14 9 10 10 4 5 5 4 6 5 6 11 9 11 8 8 10 5 8 8 4 8 12 8 4 5 8 8 7 6 5 12 3 9 6 7 6 9 9 6 7 8 5 8 9 6 7 5 4 9 9 4 7 12 9 7 7 6 8 3 3 6 5 5 9 3 5 4 4 2 6 7 6 5 11 8 6 4 6 8 5 8 1 5 3 8 10 2 4 3 8 3 10 9 5 9 7 2 4 3 9 7 5 6 9 3 10 3 8 6 2 5 4 4 6 3 3 3 9 5 3 6 6 7 6 6 9 2 4 5 7 3 5 2 1 4 7 4 4 7 2 6 3 4 5 4 3 6 3 2 3 4 2 1 2 1 10 3 6 4 4 7 2 4 4 7 4 3 3 5 6 2 8 4 4 6 3 3 3 6 3 4 6 2 11 3 2 7 6 6 1 4 5 4 3 5 4 4 5 3 0 5 3 3 4 4 3 5 0 5 1 5 5 3 4 2 8 6 4 2 3 4 4 1 2 2 2 6 5 2 2 4 3 5 3 0 3 2 5 4 2 2 1 2 0 4 2 3 2 1 5 3 4 5 3 1 0 4 2 0 3 1 1 2 4 1 3 1 3 5 5 1 3 0 2 3 2 3 0 2 3 4 1 2 3 2 2 4 3 3 2 3 2 1 1 3 1 2 4 3 4 0 2 6 4 4 1 2 1 3 0 4 6 2 1 4 1 4 1 5 3 3 4 4 3 5 5 4 1 2 1 3 4 2 4 0 0 2 2 1 2 4 1 1 1 4 1 0 2 2 5 2 2 7 4 0 1 3 1 4 1 1 2 3 0 1 4 2 0 1 0 0 2 2 2 0 3 0 1 2 2 2 0 1 1 2 1 1 1 0 4 2 0 1 1 0 3 2 0 2 
];
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
 1177096 931339 245757
 964011 763776 200235
 979765 777304 202461
 1153205 914807 238398
 1344694 1073338 271356
 805080 640118 164962
 1353213 1079244 273969
 1752099 1434165 317934
 922185 734687 187498
 1099595 884210 215385
 1594283 1301593 292690
 1301849 1045547 256302
 1284717 1051410 233307
 1056199 848284 207915
 1223619 987449 236170
 1296958 1065782 231176
 1052227 851400 200827
 1510008 1236377 273631
 1229192 993835 235357
 1234148 1018761 215387
 1083861 881703 202158
 1448646 1191895 256751
 1007389 821839 185550
 1482404 1222033 260371
 972256 794839 177417
 1330450 1105808 224642
 1410399 1164187 246212
 929222 757826 171396
 1393722 1148878 244844
 822793 667056 155737
 133038101 114947368 18090733
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
16 67 0 0
0 5 0 0
2 14 0 0
9 15 0 0
9 20 0 0
15 25 0 0
96 26 0 0
339 46 2 2
1689 67 11 10
4700 96 100 26
7839 116 663 164
16097 258 1126 551
30248 371 1910 1146
52749 673 3082 2290
91050 1308 4974 4130
198363 2691 8255 7299
925045 5388 13436 12696
5919456 10739 22287 21704
12418802 20259 39206 39086
4733077 32359 63251 63174
434786 47246 89966 89780
132759 67610 115786 116018
146565 95875 140856 141558
174121 131899 168002 169279
203623 172923 198452 199042
238616 217201 233830 234545
276568 261711 271036 270227
316140 303934 310979 310619
356162 346845 349469 351040
395057 385097 389654 389621
430200 421226 425432 426706
461305 454004 455331 455809
486893 481887 483192 482795
508572 503314 506846 506640
527127 523147 523187 526177
544606 541057 540972 542115
558987 557261 558379 557369
572503 572424 572494 572598
587829 588398 588864 587944
605093 604055 603579 605239
622001 621890 620859 622038
644015 643902 642508 643045
667883 667610 666619 666384
694514 692992 694841 695483
724549 724653 721871 724385
756193 755348 754816 757061
788165 788990 787662 787968
815338 815755 816937 818194
837670 838624 838303 838813
852052 853406 853456 854839
852359 853700 852723 854739
843772 844981 843432 845070
820142 820404 817877 820824
789471 787972 789492 788884
744403 744921 744562 746018
694859 695050 695346 695913
641223 641310 641304 640462
583622 585301 585047 584441
530841 529740 528876 530916
483887 485171 483152 484011
448787 450625 449428 447765
425598 424849 425500 425335
403879 405674 405161 405552
398966 398641 400067 400803
406498 406918 407009 405865
421198 421466 422817 423470
445174 444840 445078 445153
478745 477487 477309 478191
518917 516771 518038 518865
546028 547343 547844 549172
560305 562128 562781 562251
559947 559366 560079 560526
521841 523662 521613 522595
451801 450730 451257 451522
377457 377349 376839 377909
298769 299292 298632 298936
221810 220860 221447 221931
153259 153364 153572 152938
112954 112458 113079 113464
79323 79368 78966 79352
52719 52670 52490 53046
33198 32907 33327 32866
3161 3119 3120 3049
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
