A = [
1430838 1502766 41955184 812221 476707 422509 449057 285615 276641 251364 254187 232960 232004 232206 231522 225346 227171 226194 228488 222927 223125 223056 218712 221032 221941 258453 260442 269513 306886 307150 316658 320377 320955 331165 330071 332430 336719 338732 344317 341337 343882 350644 347575 348832 347485 350932 349952 351022 352260 352494 348799 347507 349408 348810 349181 345380 346940 344210 344805 343563 345318 342429 344004 343559 341228 342682 340764 339345 338950 337724 337747 334773 335060 336805 334490 333886 333840 331215 331917 328156 327735 329024 325319 323758 324943 321804 320607 317377 314596 315236 314220 312869 311062 308150 305646 304773 301942 300313 299230 297083 295645 293003 293181 290300 286973 284989 284158 281139 279461 276336 273532 270532 268526 265269 263658 261003 258084 256549 253826 250209 249486 243582 242855 239469 236226 234955 231189 229223 226790 224472 222110 218664 216697 213935 210931 207135 204358 203467 200915 198846 194383 193898 190680 187463 184079 181681 180837 177425 173750 171698 169194 168018 164505 163253 161133 157965 154928 153686 150481 149155 146317 143501 141482 140252 137611 135128 133430 131688 128654 127513 124551 122854 121644 118779 116620 114697 112490 110480 109475 108171 105048 103769 102009 99986 99155 96086 95747 93457 91904 90381 88926 86210 85354 83642 82432 81250 79060 76972 76275 74889 73356 72565 71105 69841 68374 67885 66030 65069 63453 62165 61900 60016 58397 57777 56878 55382 54561 53552 53102 51502 50225 49315 48242 47871 46676 45233 44779 44297 42697 42331 41372 40563 40170 38660 38545 37625 36821 36691 35872 35038 34501 33735 32755 32622 31384 31240 30247 29493 29200 28176 27738 27156 26912 25830 25297 24963 24286 24044 23442 23032 22434 22126 21555 21337 20713 20287 20011 19261 19355 18652 18352 17903 17720 17434 16760 16513 16210 15872 15476 15202 15038 14589 14210 14082 13804 13386 12570 12608 12466 12068 11888 11618 11553 11212 10771 10779 10324 10096 9635 9356 9330 9082 8801 8621 8450 8090 7809 7894 7638 7495 7246 7374 7085 6805 6672 6382 6345 6192 6344 6043 5867 5784 5665 5524 5211 5365 5065 4992 4852 4708 4622 4444 4588 4467 4401 4289 4258 3991 3868 4007 3843 3865 3840 3595 3611 3505 3354 3374 3234 3097 3111 3072 2865 2937 2783 2585 2675 2670 2491 2468 2383 2390 2341 2280 2252 2202 2185 2142 2083 1989 1926 1913 1880 1831 1785 1727 1674 1593 1682 1603 1541 1431 1582 1470 1411 1354 1323 1404 1285 1203 1223 1151 1179 1196 1129 1110 1035 976 995 1057 1035 983 949 900 885 903 824 829 713 780 741 718 724 739 686 675 700 630 646 633 642 638 629 620 576 607 593 546 545 501 493 472 466 458 430 424 419 413 406 371 373 402 397 418 346 340 356 501 331 326 329 329 343 351 347 361 332 360 340 334 267 300 301 265 256 254 304 260 268 246 256 279 252 253 223 234 241 247 216 229 190 207 232 189 198 214 174 184 158 196 163 173 212 196 207 151 166 174 157 142 153 156 163 146 151 131 126 142 117 128 151 111 131 109 113 117 125 138 123 116 122 121 107 123 142 108 107 109 105 118 115 105 121 93 98 111 105 97 111 90 93 89 97 85 119 78 95 76 83 88 75 103 95 92 78 87 77 102 83 102 70 81 85 71 73 83 77 68 84 71 73 72 78 69 89 72 124 79 89 95 96 70 119 58 55 60 60 53 75 79 80 60 51 81 76 53 62 59 83 69 54 54 58 44 56 51 66 71 72 59 56 77 64 75 59 84 66 57 71 53 56 60 88 58 69 51 57 49 49 59 62 52 48 56 56 35 45 33 45 58 68 43 52 61 74 35 50 55 43 53 59 48 50 51 39 39 56 66 38 36 41 96 37 43 34 51 49 35 54 43 43 34 43 33 75 39 44 46 39 42 35 47 31 40 37 23 37 42 38 46 36 33 41 35 47 38 41 41 57 34 39 35 29 42 37 43 32 40 38 33 39 35 32 37 28 33 38 27 39 39 27 33 43 39 34 45 32 28 27 36 30 40 36 27 31 43 33 35 26 25 31 37 31 18 46 31 22 21 40 35 32 23 32 33 36 26 35 26 44 39 33 18 36 22 28 25 30 12 24 32 27 33 20 28 24 28 23 30 34 28 25 32 22 25 28 23 25 25 33 27 30 27 17 29 39 38 32 31 28 38 35 34 36 25 24 29 30 31 24 18 20 32 26 21 28 23 25 32 36 25 28 12 32 22 23 30 26 17 23 22 16 23 22 14 22 24 25 18 33 44 21 8 21 10 20 20 13 11 18 15 27 24 20 19 18 12 16 18 14 17 12 22 23 19 18 22 17 31 14 19 23 13 22 14 16 13 15 15 17 16 22 15 14 23 16 13 20 17 16 14 13 13 18 14 16 19 15 11 11 8 15 15 12 11 14 19 10 16 13 14 23 16 19 17 20 11 10 14 15 16 23 9 16 18 16 17 15 17 8 12 10 7 9 7 10 13 20 8 23 10 11 13 10 14 7 13 18 12 23 15 20 30 33 19 14 14 21 18 23 16 25 18 13 21 18 20 36 22 14 14 21 19 25 15 15 17 13 33 12 18 18 14 8 7 17 9 7 8 11 6 12 13 8 9 17 11 8 11 12 12 23 14 13 15 9 15 14 14 20 15 12 13 8 11 13 18 15 18 26 15 9 8 6 8 4 8 5 8 6 10 5 10 9 8 6 10 9 8 12 13 14 5 10 10 21 6 6 18 6 10 9 5 4 6 12 8 4 9 5 7 4 10 15 11 13 8 4 10 5 3 7 2 6 5 9 10 4 5 7 9 9 7 8 2 12 8 2 5 5 7 8 9 9 13 7 2 6 10 7 7 6 5 3 11 13 6 9 9 5 6 3 2 5 6 5 4 2 7 7 12 8 9 11 4 11 4 6 5 2 8 1 4 8 5 2 1 6 8 6 6 3 4 4 4 8 3 4 8 4 0 7 8 7 8 1 2 8 6 4 8 9 4 3 7 6 6 8 5 11 5 8 5 9 0 5 6 4 7 10 5 5 23 9 9 3 0 4 7 7 4 12 7 9 6 7 8 5 8 11 8 5 4 4 3 1 9 4 5 4 5 1 7 6 10 9 7 5 4 10 3 7 3 3 3 3 8 5 5 0 3 3 9 8 5 6 4 6 4 5 7 6 9 6 1 7 2 9 5 2 3 5 4 5 4 2 4 4 7 4 3 6 4 7 10 5 2 8 8 2 2 6 2 2 6 7 8 3 1 1 4 5 5 2 3 2 4 5 4 1 5 5 0 6 7 5 6 2 2 4 3 5 2 11 1 2 6 8 2 3 2 1 5 5 7 6 3 0 2 3 4 2 2 13 2 5 1 2 2 4 4 3 0 4 4 2 5 4 1 5 4 0 7 1 4 0 4 2 1 2 3 2 3 2 1 1 4 4 2 4 2 28 4 6 1 1 0 4 5 4 7 14 5 3 2 5 0 1 5 2 1 2 0 2 1 3 1 5 4 1 0 6 0 1 2 0 0 0 1 1 3 0 2 1 1 2 3 8 1 2 1 2 2 3 2 4 1 1 0 2 1 1 2 1 3 3 1 3 2 2 4 3 0 2 2 0 1 4 2 1 2 0 0 1 4 2 8 21 3 0 0 2 1 1 0 0 2 3 1 2 0 2 4 2 1 0 2 1 1 2 1 0 2 0 4 0 1 0 2 0 0 1 1 2 0 2 0 0 1 0 2 2 1 2 1 0 0 3 0 10 1 1 0 2 2 2 0 0 2 1 1 3 0 3 2 1 3 0 1 1 1 1 2 2 2 0 0 0 2 1 2 0 0 1 1 1 1 1 1 0 1 4 0 2 0 0 1 2 0 2 1 2 0 1 1 1 2 0 0 1 0 0 1 0 2 2 0 1 0 0 1 0 3 1 0 0 2 1 0 1 1 1 0 0 0 0 0 2 1 1 0 0 1 0 1 0 3 1 1 1 1 0 2 1 2 3 0 1 1 3 1 0 0 0 1 0 1 1 1 0 3 0 1 0 2 2 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 1 0 1 0 0 1 0 0 1 0 0 0 0 2 1 1 0 0 0 1 0 0 0 1 2 2 1 2 1 0 0 0 0 1 0 2 1 3 0 0 1 6 0 0 0 2 0 0 1 0 0 3 0 0 0 0 1 0 0 2 1 0 0 1 0 1 1 4 0 1 0 0 0 0 0 0 2 1 1 1 0 1 0 0 0 1 1 0 0 1 0 0 1 1 1 2 1 1 0 0 1 0 1 0 0 2 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 1 2 1 1 0 2 1 0 2 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 1 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 0 1 0 0 0 1 0 0 0 3 0 0 0 0 0 1 0 0 0 0 0 1 2 1 0 1 0 0 0 1 0 0 1 0 0 1 0 2 0 0 2 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 4 1 1 2 0 0 2 0 0 0 0 2 0 0 0 0 0 1 0 2 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 0 0 2 0 2 0 0 0 0 1 0 1 2 0 0 0 1 1 3 0 0 0 0 0 1 0 0 0 
];
B = [
0 0 0
 357940 332786 25154
 176067 162747 13320
 457776 427363 30413
 390374 365698 24676
 208698 195876 12822
 560333 523948 36385
 288487 272412 16075
 434730 412932 21798
 558257 527004 31253
 204855 195635 9220
 782368 698889 83479
 479633 436609 43024
 125682 118922 6760
 381366 367658 13708
 267896 259181 8715
 74570 71513 3057
 429914 414523 15391
 186466 181660 4806
 29207 27867 1340
 15082 14275 807
 6591 6171 420
 7591 7368 223
 660284 637024 23260
 293649 286613 7036
 51874 49858 2016
 687425 663827 23598
 325814 317509 8305
 58510 56653 1857
 995507 960705 34802
 441088 430414 10674
 93817 90882 2935
 798991 774433 24558
 429410 421130 8280
 938563 910858 27705
 329030 324609 4421
 625800 615726 10074
 1439419 1395509 43910
 455086 448454 6632
 1104729 1088367 16362
 1575606 1530872 44734
 553098 543093 10005
 1245598 1220757 24841
 1600823 1565291 35532
 401246 393573 7673
 1725923 1698854 27069
 2137950 2093620 44330
 387453 374345 13108
 2572621 2548309 24312
 4315439 4233456 81983
 78902 76442 2460
 4744725 4699322 45403
 7182483 7063093 119390
 239823 232346 7477
 1 1 0
 11698350 11510220 188130
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
35 43 0 0
8 4 0 0
17 9 0 0
18 28 0 0
20 5 0 1
101 21 112 4
33041 60 358 57
262223 32 425 91
765393 40 532 159
1550817 48 693 287
2626923 71 794 372
4665535 113 964 551
7014244 167 1048 710
9121654 292 1174 926
9212377 430 1287 1131
7762540 699 1531 1463
4982877 990 1955 1842
2379651 1055 2286 2286
781074 1423 3132 3016
148822 2109 3746 3679
17797 2968 4534 4579
6147 3779 5491 5298
6593 5070 6529 6478
7542 6676 7670 7624
8830 8102 8802 8752
9932 9576 10133 10242
11431 11598 11699 11695
12815 13381 13204 12979
14560 14914 14576 14821
15772 16456 16215 16435
16992 18254 17539 17566
18825 19257 18606 18484
19215 20414 19831 19613
20189 20748 20549 20307
20429 21715 20765 20946
21018 21232 21299 21061
20896 28049 21273 21463
20645 21400 21075 20652
20805 21299 20692 21201
20784 21074 20873 20808
21172 21098 20962 21215
21688 22065 21602 21640
22368 22078 21950 21945
22982 23123 23036 22928
23844 24195 23931 24075
25256 25521 25047 25209
26495 26633 26662 26737
27611 27713 27738 27525
28712 28508 28692 28652
29507 29425 29417 29642
29610 29418 29663 29794
29426 29640 29420 29564
28568 28922 28867 28578
27480 27440 27729 27692
26044 25774 26217 26033
24093 24365 24287 24156
21656 22088 22014 21695
19527 19908 19797 19738
17578 17863 17920 17614
15858 15895 16231 15970
14196 14282 14227 14388
12716 12659 12680 12579
11449 11584 11738 11659
11107 11117 10964 11029
10347 10672 10532 10681
10421 10245 10524 10309
10723 11130 10927 10715
18326 18979 13428 12653
11677 11561 11569 11597
12019 12110 11970 11908
11307 11385 11231 11171
10068 9983 10302 10248
10544 10623 10687 10765
7058 7199 7296 7202
6072 6034 5988 5943
5007 4953 4782 4746
4041 3979 4068 4061
3378 3435 3503 3418
2840 2920 2875 2923
2175 2220 2213 2381
1431 1447 1428 1430
735 747 792 739
44 34 35 29
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
