A = [
1764183 2091998 29623808 851341 852072 827161 661438 709531 642621 501597 482098 469255 462527 458727 452334 448453 446397 443535 442118 438253 435491 433116 429422 427366 429394 507766 507921 518689 598201 602048 611876 615885 616503 618658 621343 619691 616728 615517 616579 611467 610152 612368 606166 604828 606952 601432 598244 600416 596521 592165 593076 587757 587988 584663 579896 577856 574040 574486 568946 568096 566204 563301 559251 558063 554735 553172 550459 547906 547039 545201 543953 542367 541794 540347 540238 538302 536085 533519 531355 527337 525697 524025 519829 515596 513328 509799 506066 501513 497852 494645 491092 486895 483233 479535 476366 474427 470163 467099 462263 459504 457048 453283 450520 448373 444764 441687 437997 435948 431704 426717 423560 421843 418823 416583 412771 410586 406576 402719 400996 396735 394199 391993 387183 385868 381298 378873 375283 373157 368751 366328 362939 360116 357386 354223 352284 348734 346381 343529 340061 336942 334551 331932 329460 326143 323449 321162 318176 315157 312378 309437 305720 304305 302888 298742 295905 293450 290588 286691 285684 281781 279845 279269 276000 272883 271203 267767 266422 262785 261093 257659 255601 254941 250299 249694 246122 244618 241345 239978 237707 235089 232873 230037 228617 226838 224540 221940 220270 218103 216061 215792 212108 210123 208126 205991 204622 201894 200755 197847 196421 195161 191914 190831 188666 187002 184662 182666 181570 179344 177483 175798 174719 172023 171160 168729 167206 166029 164077 162253 160942 159404 158118 156293 154816 152968 151040 149548 148259 147875 145783 144259 143057 140891 139822 137958 137111 135198 133387 132075 130556 129744 128220 126498 125187 124657 122864 121224 119606 119943 118170 116634 115150 114124 112792 111805 110601 109397 108138 106557 105915 104462 103116 102455 101354 99889 98817 97452 96770 95032 94599 93419 91855 91085 89714 89119 88321 87106 85965 84820 83913 83089 82304 80488 80321 79447 77971 77135 76225 75986 74158 73316 72825 72331 71340 69959 69302 68392 67495 66948 66363 65858 64571 63497 63383 62160 61346 60560 59630 59243 58320 57701 56821 56462 55743 54934 53869 53822 52783 52084 51866 51488 50343 49796 48861 48391 47947 47374 46800 45815 45647 44967 44042 43639 43296 42591 42139 41943 40954 40612 40282 39576 39139 38631 38577 37475 37365 36791 35679 35684 35300 34754 34139 33979 33212 33219 32822 32406 32121 31197 30904 30491 30222 29802 29393 29044 28614 28270 27940 27256 27102 26796 26241 26347 25927 25358 25181 24900 24512 24408 23924 23413 23369 22999 22678 22062 22112 21648 21157 21202 21027 20534 20081 19951 19995 19540 19284 18889 18832 18337 18140 17848 17964 17498 17266 16887 16861 16506 16462 16226 15779 15852 15505 15448 15246 14763 14526 14459 14339 13975 13988 13607 13526 13342 13070 12949 12848 12424 12355 12099 12109 11814 11911 11492 11373 11234 11342 10947 10794 10474 10730 10354 10104 9788 10115 9854 9568 9687 9436 9287 9089 8861 8899 8871 8625 8658 8501 8442 8286 8188 8069 7854 7753 7515 7573 7447 7149 7095 7033 6992 6939 6900 6773 6627 6518 6639 6339 6316 6224 6147 6053 6084 5840 5751 5624 5586 5692 5419 5540 5368 5214 5216 5191 5118 5004 4908 4926 4754 4645 4742 4570 4510 4454 4436 4320 4292 4169 4120 4089 3998 3873 4037 3936 3793 3696 3767 3673 3671 3721 3465 3516 3362 3405 3311 3244 3325 3260 3152 3049 3109 3059 2883 2955 2904 2897 2781 2870 2749 2715 2667 2575 2624 2617 2555 2512 2527 2490 2487 2352 2462 2308 2310 2394 2198 2220 2209 2153 2113 2105 2075 2082 2123 2000 2014 1967 1934 1881 1937 1863 1829 1794 1834 1737 1657 1674 1673 1638 1597 1661 1630 1619 1652 1623 1484 1586 1496 1523 1431 1429 1453 1448 1406 1385 1337 1353 1396 1365 1316 1356 1242 1238 1157 1214 1236 1253 1225 1159 1174 1188 1244 1181 1162 1087 1080 1121 1057 1035 1093 1046 977 1053 989 1016 1021 982 981 947 952 972 960 947 881 957 908 892 919 880 811 857 811 852 824 766 835 811 815 760 794 795 777 795 791 692 720 790 758 755 740 747 687 677 742 669 690 668 656 692 693 651 650 650 624 669 648 634 645 609 637 585 589 594 611 610 621 579 597 538 519 580 522 596 548 586 519 507 538 530 515 515 518 494 488 465 464 497 510 511 499 512 501 457 535 451 480 502 438 455 461 446 456 427 424 433 438 477 443 445 406 440 424 445 420 418 436 392 423 433 424 385 432 397 412 384 385 394 406 374 402 403 374 377 369 380 347 345 359 372 372 383 324 325 347 358 362 318 342 318 337 339 315 349 289 335 316 316 330 311 357 317 319 327 306 297 328 320 308 305 294 273 304 279 292 300 309 291 320 298 298 278 264 258 293 305 285 270 269 300 261 297 286 257 272 256 259 264 276 267 280 242 270 221 238 302 241 249 224 255 246 237 272 261 221 236 232 264 254 227 238 221 259 223 224 238 229 221 213 229 232 227 211 202 239 221 209 217 226 210 246 199 195 224 217 213 246 189 233 235 208 198 200 219 207 186 226 199 180 210 174 175 217 187 180 198 174 205 171 211 197 201 185 161 181 198 184 194 173 184 186 211 170 171 175 179 191 174 171 183 159 189 184 161 132 150 183 179 163 171 156 168 146 173 168 152 176 166 162 177 153 156 155 176 166 145 156 164 148 183 163 139 130 139 152 159 167 154 139 169 155 146 162 139 139 145 148 153 144 141 133 143 141 140 132 145 121 164 130 140 159 135 141 131 126 139 142 116 135 150 108 141 126 134 127 136 134 116 114 123 128 118 112 110 114 132 114 113 114 126 129 140 118 104 129 129 109 114 134 122 118 115 120 108 115 109 100 94 112 108 101 108 101 106 108 110 100 106 111 93 91 96 103 88 110 91 107 106 82 110 95 112 93 96 101 101 90 97 101 88 102 98 85 81 92 100 93 111 86 82 90 95 76 99 100 82 91 98 69 78 109 79 72 72 80 91 105 81 85 80 72 89 91 81 73 100 79 79 79 90 75 84 73 80 63 83 81 78 77 64 73 61 66 84 55 55 70 65 76 68 71 69 76 75 65 59 78 79 56 68 70 74 77 60 74 67 70 77 95 62 76 62 67 75 66 69 67 68 63 61 63 57 70 51 58 68 54 60 75 51 53 62 65 51 49 63 59 57 56 77 53 58 51 49 61 51 54 56 53 56 54 49 60 56 63 49 44 56 51 54 49 66 41 57 60 37 63 53 61 44 45 38 45 48 51 57 51 44 46 47 58 39 48 49 50 47 49 56 44 44 58 47 47 38 42 50 44 43 36 39 46 54 44 42 49 44 48 38 45 40 39 37 43 38 41 30 54 37 30 51 41 43 52 37 42 49 36 47 35 41 46 39 42 34 34 41 32 50 54 40 34 29 27 49 38 33 40 47 35 37 34 37 40 25 38 36 38 35 39 35 26 36 29 41 32 31 47 39 26 29 40 23 26 30 33 28 35 26 38 20 27 33 38 44 22 37 38 28 29 25 28 24 39 27 27 29 29 33 26 31 29 19 32 29 34 27 23 28 28 35 25 26 19 24 32 27 27 32 29 21 25 32 22 15 23 27 38 29 23 29 24 22 29 19 20 19 22 21 27 18 24 24 30 24 29 16 23 29 26 14 25 27 31 20 24 14 20 23 22 16 18 22 19 18 27 23 19 13 23 23 21 19 28 21 12 28 19 17 17 20 18 20 26 20 18 20 16 22 16 29 17 18 20 20 23 18 16 22 17 16 21 21 17 11 12 19 21 15 18 19 16 17 15 21 14 18 19 16 13 17 23 20 11 17 18 17 13 16 15 18 14 14 16 13 14 15 16 16 16 8 15 19 10 16 21 22 18 20 15 12 14 19 14 17 20 9 13 19 17 19 15 9 14 17 20 19 15 19 16 11 14 11 16 13 9 14 12 26 15 13 11 12 15 11 14 10 14 11 14 14 9 14 14 15 17 15 14 15 17 13 11 16 8 19 16 10 10 8 17 15 12 15 11 10 6 11 14 10 14 14 10 8 12 8 12 9 11 6 9 5 6 11 15 10 9 15 9 13 7 11 12 5 21 9 6 9 14 12 11 12 14 14 10 13 8 9 9 8 3 11 6 8 15 10 15 15 5 12 11 15 8 17 11 7 9 7 14 5 12 8 11 14 10 15 6 8 7 4 5 8 15 12 10 5 12 4 10 1 10 10 9 3 5 6 10 11 15 9 9 8 13 7 8 8 4 4 11 5 6 8 8 9 12 7 6 9 4 10 8 9 12 8 6 8 6 8 4 7 8 4 7 5 11 10 4 7 10 4 4 4 7 3 5 7 5 3 4 8 6 6 3 10 9 8 4 7 9 12 7 10 10 1 7 7 2 4 5 1 6 2 8 1 5 3 5 1 5 9 7 7 6 8 5 3 4 5 4 4 5 6 3 9 3 6 4 5 8 2 8 9 5 6 9 6 5 4 4 4 4 2 9 6 7 4 4 4 3 5 2 3 11 5 3 3 6 6 7 6 3 3 9 4 7 6 4 10 7 6 3 4 2 4 4 8 3 6 5 3 2 4 6 2 8 3 8 5 6 3 1 5 6 6 4 2 6 4 5 6 6 5 2 6 3 4 5 5 7 6 3 2 7 3 1 3 8 2 9 5 7 2 2 4 4 3 4 3 5 3 3 5 2 4 1 5 3 8 8 1 2 2 6 4 6 5 6 1 4 7 3 5 7 6 4 5 4 5 5 4 7 1 3 3 4 3 3 0 3 2 6 1 1 5 4 1 2 3 5 4 3 6 3 2 2 2 4 2 2 4 3 3 1 1 4 4 3 5 1 5 1 1 4 3 4 3 3 5 5 4 5 3 3 0 2 2 3 1 3 2 3 6 1 4 1 3 7 3 2 1 4 1 4 4 2 4 5 4 3 4 0 2 4 7 2 1 3 3 1 4 3 2 5 2 3 0 1 1 4 3 3 1 3 3 1 3 1 2 3 0 3 5 3 1 2 1 1 0 1 4 1 1 1 1 3 5 4 1 1 1 2 1 1 1 3 0 2 1 3 4 1 2 2 2 3 2 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
 2922737 2541209 381528
 196998 176750 20248
 331096 298428 32668
 2458385 2179023 279362
 621114 562885 58229
 929622 845481 84141
 3393033 3036203 356830
 1423727 1285863 137864
 838757 762305 76452
 4121366 3710757 410609
 853539 771376 82163
 163565 147543 16022
 5397936 4886067 511869
 85323 76623 8700
 137903 123355 14548
 9230781 8421834 808947
 153661 138795 14866
 518470 459170 59300
 14849630 13631313 1218317
 499088 450479 48609
 4 4 0
 25429401 23392904 2036497
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
163 537 1 0
9 75 0 0
43 74 0 0
64 104 0 0
31 106 1 1
53 112 702 38
1486 130 1990 196
17273 143 2592 449
93732 191 3411 680
298518 205 4521 1165
631845 234 5478 1487
1271114 309 7068 2359
2212258 478 8093 3170
3666395 873 9848 4546
5314751 1406 11412 6007
7172540 2327 12632 8090
8341316 3658 14218 10381
8280892 5509 15687 13619
6636235 8040 18692 17947
3801008 11297 22762 22522
1365981 15219 27384 27485
254623 20322 32862 32734
50342 27555 38675 38191
46053 35723 44604 44795
51931 44868 51678 52176
58911 54539 58608 59489
66672 64254 67303 67425
74277 74441 75493 75931
82157 83492 84113 84609
90640 91437 91545 92644
97512 100133 99488 99889
103929 105672 104906 105362
107296 110966 109261 110341
110842 115353 113532 113485
112222 117392 114865 115289
113393 117571 115037 115560
112254 116569 113986 114757
111337 114389 112260 112797
109098 111508 110599 111170
108422 110612 109117 109519
107208 109643 108762 108159
108306 109411 109201 109708
110707 111080 110334 110775
112955 114314 113755 114029
117729 117845 117211 117746
121797 121879 121761 122299
125091 126486 125428 125788
129085 128701 128575 128990
130224 131520 130512 131352
131128 131162 130065 131053
127820 128896 128382 128809
123353 125140 123563 124175
116979 118840 116705 118120
109233 111171 110472 110699
101343 102928 102174 102065
91962 93741 92933 92831
82823 85185 83663 84034
74791 76169 75392 75703
68000 68484 67967 67969
60854 61667 61203 61745
56576 57286 56589 57123
53076 53701 53756 53372
48771 49028 49013 49030
46006 46627 46490 46340
44283 44433 44060 44370
43439 43401 43555 43569
43363 43530 43382 42957
43890 43310 43517 43579
43533 43344 43206 43578
42602 42616 42290 42462
41542 41359 41349 41357
39800 39840 39482 39951
37806 38290 37632 38071
35296 35431 35680 35683
31495 31747 31519 31661
28009 28124 28413 28121
23241 23252 23229 23455
17298 17456 17302 17450
14092 14116 14034 14257
10472 10353 10182 10294
6170 6142 6191 6111
3447 3481 3572 3474
161 172 167 158
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
