A = [
2050842 2431792 34666944 986259 1006667 974743 803140 870066 764825 619748 599863 560288 548643 542880 534963 530637 528606 524615 522925 518747 515391 512747 508408 506201 508544 600943 601404 614196 708941 713289 724448 730599 730136 734477 736847 735437 732385 730972 732127 726225 724904 727015 719673 718371 719570 714128 711043 712605 708540 702983 704520 698400 698382 693582 688775 686264 681989 682406 676188 674216 672618 669490 664885 663357 659101 657095 653725 650409 649057 647752 645615 645055 643410 641603 641459 638473 637169 633813 631441 626754 625038 622413 617474 612918 609542 605533 601708 596377 592118 588142 584194 578885 574922 569811 566042 563479 559169 555367 549710 546260 543425 539043 535994 532504 528680 524399 520895 517443 512991 507322 503183 501668 497432 494853 490576 487646 483180 478628 475815 471508 468115 464835 459701 458092 453320 450038 445682 442657 438278 435528 430909 427341 424372 421387 417990 414171 410799 407311 403515 399811 397427 393448 390458 386881 383414 381153 377072 373755 370364 367371 362792 361047 359072 354151 350810 347959 344165 340108 338597 334205 331274 330551 326565 322747 320823 316945 315121 311385 309032 305208 302712 301057 296160 295530 291258 289263 285697 283454 281250 278005 275469 272040 269958 267935 265473 262487 260139 257366 255153 254720 250528 247892 245573 243146 241904 238231 236885 233920 232048 229942 226547 225182 222478 220602 217666 215323 213912 211479 209380 207493 205991 202996 201547 198618 197199 195632 192944 190792 189822 187423 186004 184340 181901 179933 177912 175543 174500 173711 171668 169888 168131 165201 164351 162055 160807 158737 156847 155167 153431 152139 150630 148632 147026 146286 144348 142180 140457 140461 138238 136423 135118 133712 132044 130905 129895 127859 126427 125030 123676 122380 120886 119628 118608 116771 115654 113997 113083 111165 110575 109180 107416 106647 104844 104037 103167 101599 100352 99028 97914 96873 95831 94089 93588 92796 90974 89905 88887 88282 86479 85371 84904 84352 83200 81607 80924 79704 78458 77891 77121 76487 75226 73884 73589 72357 71383 70269 69315 68900 67776 66896 66098 65424 64764 63786 62597 62330 61354 60360 60180 59648 58206 57609 56628 56128 55597 54930 54296 53126 52715 51826 50975 50620 49935 49228 48548 48423 47359 46941 46417 45777 45065 44524 44496 43308 43088 42429 41297 41050 40630 39907 39352 39094 38200 38021 37693 37343 36930 35860 35666 35185 34652 34040 33823 33355 32834 32448 32135 31312 31061 30706 30152 30070 29511 29081 28892 28509 27958 27985 27290 26716 26585 26232 25948 25184 25223 24823 24175 24165 23999 23505 23017 22642 22810 22360 21903 21467 21488 20798 20568 20280 20345 19849 19487 19147 19100 18773 18706 18369 17929 17958 17545 17500 17308 16775 16451 16365 16259 15805 15837 15384 15315 15066 14708 14733 14463 14127 13961 13663 13653 13366 13395 13011 12897 12719 12707 12332 12205 11854 12042 11669 11382 11061 11390 11041 10730 10857 10552 10433 10221 9967 9930 9921 9679 9688 9499 9513 9288 9157 8972 8760 8673 8431 8461 8317 7997 7963 7891 7827 7761 7732 7576 7389 7259 7365 7054 7044 6956 6871 6712 6760 6517 6359 6320 6228 6320 6086 6116 5942 5809 5757 5731 5702 5596 5524 5484 5292 5177 5248 5083 5005 4951 4917 4773 4789 4612 4511 4513 4455 4319 4470 4350 4237 4121 4167 4106 4081 4139 3832 3886 3718 3775 3643 3607 3660 3596 3478 3436 3462 3394 3209 3286 3233 3195 3108 3175 3056 3013 2962 2838 2906 2909 2847 2798 2793 2740 2734 2602 2688 2564 2562 2643 2433 2441 2453 2390 2327 2336 2312 2293 2344 2214 2239 2194 2155 2092 2170 2068 2036 2016 2036 1929 1852 1853 1856 1833 1767 1844 1824 1811 1825 1806 1662 1767 1658 1682 1602 1577 1633 1595 1559 1570 1478 1543 1548 1543 1469 1505 1411 1366 1310 1372 1368 1401 1369 1286 1326 1329 1377 1308 1318 1237 1223 1252 1186 1189 1227 1178 1096 1179 1107 1129 1143 1115 1121 1075 1072 1076 1083 1068 988 1084 1041 1015 1034 994 935 973 909 982 948 868 946 932 932 858 900 916 865 887 888 791 828 873 852 852 849 846 793 801 845 791 801 786 756 792 769 747 746 743 726 772 741 727 740 706 715 662 680 673 698 699 702 664 699 635 611 667 613 675 642 668 598 572 625 617 605 599 612 579 579 534 545 592 608 578 576 578 577 539 610 538 565 583 509 513 536 517 532 514 489 506 512 553 511 510 476 511 503 506 480 502 484 466 493 493 511 454 509 472 488 449 458 450 473 430 464 470 443 443 433 445 421 402 423 442 428 448 383 395 400 418 431 377 406 386 399 405 391 406 349 394 370 381 394 368 411 384 388 379 354 350 396 368 375 364 334 352 368 327 342 356 379 342 358 346 349 327 308 299 353 357 343 321 329 341 321 336 329 310 318 317 316 310 315 311 325 290 330 282 292 342 287 308 262 287 294 274 308 308 267 267 279 306 299 272 282 256 311 267 269 287 272 273 241 274 282 270 254 236 286 271 244 256 264 239 288 246 234 265 252 255 284 223 271 272 256 245 237 263 242 225 266 238 218 242 208 205 258 216 208 236 210 234 194 246 235 229 223 198 218 226 217 235 198 219 212 239 203 205 205 221 221 210 197 206 203 218 213 189 175 181 226 213 197 195 181 203 173 208 199 178 202 197 198 208 178 188 182 201 195 177 181 201 177 215 186 172 162 164 180 186 191 174 161 191 175 170 183 163 170 171 172 185 183 177 154 171 162 162 163 173 151 186 154 173 173 155 172 155 147 160 171 139 148 179 141 161 156 160 143 156 163 144 136 146 154 131 126 139 136 157 138 133 131 147 151 166 144 128 155 152 131 129 156 151 139 128 141 127 136 123 115 108 135 128 117 122 115 120 129 123 121 130 131 111 112 114 123 104 131 113 119 124 98 121 106 135 115 113 113 119 107 117 119 104 120 120 100 98 112 122 109 125 100 102 106 115 90 123 116 101 101 109 84 93 125 99 92 84 95 106 119 96 100 94 83 101 104 94 94 117 90 93 89 97 90 96 91 95 74 95 95 88 83 76 91 71 84 96 66 70 85 79 90 76 80 92 88 89 78 72 89 96 68 81 78 87 91 75 84 76 86 94 107 72 84 73 80 90 76 80 82 83 73 70 77 73 86 62 74 78 68 80 83 61 63 77 78 67 62 72 70 69 68 89 59 71 69 56 74 55 61 65 61 59 60 59 69 64 77 60 52 70 63 60 64 76 46 76 70 51 75 63 68 53 51 44 51 56 58 73 61 50 55 52 69 48 55 60 55 57 61 63 50 52 65 55 52 44 50 56 51 53 49 51 56 67 48 54 54 50 53 44 48 47 45 43 51 46 47 41 60 45 40 58 51 49 62 43 51 53 50 54 51 51 59 46 52 41 40 47 38 58 59 50 42 36 32 60 47 40 43 57 41 45 37 42 48 35 44 44 43 37 44 37 34 41 33 48 35 36 52 45 34 36 48 27 30 35 42 31 44 28 42 27 33 40 46 53 29 43 41 33 36 31 31 31 45 31 36 38 32 35 32 33 34 27 40 34 36 32 31 35 33 41 30 31 22 34 38 27 29 35 33 28 26 38 27 19 27 29 41 36 29 35 29 29 34 25 26 25 27 25 32 22 27 26 35 27 34 19 28 32 28 17 28 31 35 25 27 20 26 26 25 18 23 26 21 20 29 29 20 15 26 25 23 25 30 23 13 36 21 20 22 21 23 20 30 22 22 25 23 24 21 30 25 19 23 25 25 20 19 23 23 19 25 22 19 14 14 20 25 20 22 21 17 18 18 24 17 21 23 19 22 18 26 24 12 19 23 18 15 19 19 19 16 15 23 14 21 20 16 22 16 11 16 25 14 23 25 26 19 23 17 13 18 25 18 20 26 12 16 19 21 25 17 12 17 23 21 21 17 19 20 13 15 11 17 17 10 15 14 28 17 18 14 15 18 13 15 11 17 14 16 19 10 19 17 15 17 18 17 17 20 14 14 16 11 20 17 15 12 10 21 18 13 16 11 12 8 13 16 11 18 17 11 12 14 9 12 13 14 8 15 7 7 15 16 10 9 16 10 15 10 14 14 12 23 10 9 11 19 14 12 12 14 20 12 13 10 14 10 13 4 13 6 10 18 10 17 15 7 12 14 16 9 20 12 7 9 8 15 5 12 9 12 16 11 17 9 9 10 6 6 11 16 13 11 5 15 4 11 1 11 12 13 4 6 8 13 12 15 9 11 9 14 7 10 9 7 4 14 6 7 9 12 11 12 8 6 9 5 10 9 10 15 8 6 9 7 10 5 8 10 5 8 8 12 11 4 7 10 4 5 6 10 3 7 10 5 5 6 9 6 10 3 12 9 8 6 9 11 13 9 11 11 3 8 7 3 5 6 4 7 2 11 5 5 4 7 1 5 9 8 8 8 8 5 4 4 6 5 4 6 9 6 9 4 7 5 5 11 2 8 10 5 8 9 8 6 4 4 4 8 3 9 6 7 4 4 6 4 6 3 4 12 5 4 4 9 8 8 7 4 4 12 5 8 6 4 10 9 7 3 4 3 4 4 8 4 7 5 5 2 4 8 2 10 5 8 6 8 3 3 5 7 6 3 3 10 5 5 7 6 7 2 7 3 5 6 5 8 7 5 3 7 4 2 4 8 2 10 6 8 2 2 4 4 3 4 3 5 3 3 5 2 5 4 5 4 9 10 1 2 2 6 5 7 6 6 2 4 8 4 5 7 6 5 6 4 6 6 4 8 2 3 4 4 5 3 0 5 2 6 1 1 6 5 3 2 3 6 4 4 7 3 4 2 2 4 2 3 5 3 3 2 1 4 4 3 5 1 5 1 1 7 4 6 6 3 6 6 5 6 4 3 1 3 3 4 1 3 3 5 6 1 4 1 3 7 4 2 3 4 2 4 4 5 4 7 5 4 5 1 2 4 7 3 2 3 3 1 4 4 2 6 2 4 0 1 1 6 3 3 1 3 3 1 3 2 3 3 1 3 5 3 1 5 1 1 0 1 5 2 2 2 1 3 5 7 2 1 2 2 1 4 2 3 0 3 2 4 4 1 2 2 2 5 2 4 
];
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
 2877994 2497366 380628
 259932 232607 27325
 752099 669680 82419
 2480514 2196099 284415
 1112488 998664 113824
 1061699 964081 97618
 3423897 3059934 363963
 2247629 2024875 222754
 1076439 978059 98380
 4411276 3970069 441207
 1780397 1607228 173169
 590194 537113 53081
 5623643 5083212 540431
 908644 821749 86895
 430763 391036 39727
 9190806 8370326 820480
 1043599 949071 94528
 710075 632428 77647
 14482424 13272400 1210024
 2169032 1981058 187974
 38894 35356 3538
 24884629 22855336 2029293
 2492902 2298421 194481
 107132 97136 9996
 1 1 0
 3674166 3392951 281215
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
187 626 1 0
13 87 0 0
50 83 0 0
76 126 0 0
37 121 2 1
64 128 820 43
1742 155 2385 226
20557 163 3132 537
111620 220 4122 829
355963 237 5495 1384
754455 274 6576 1794
1516292 384 8501 2833
2638207 580 9873 3862
4366689 1024 11810 5393
6329283 1666 13491 7120
8538064 2786 15066 9619
9910496 4320 16741 12325
9775449 6480 18554 16170
7694724 9600 21941 21228
4241226 13299 26984 26621
1450960 17869 32326 32531
265891 23900 38819 38789
57822 32433 45664 45244
54261 42147 52756 52970
61266 52862 60921 61634
69598 64349 69473 70053
78744 75931 79579 79887
87815 87886 89306 89728
97349 98758 99547 99995
107240 108135 108374 109535
115231 118347 117483 118078
122820 125300 124088 124644
126728 131352 129342 130514
130885 136242 134150 134191
132614 138678 135848 136233
133998 138792 135948 136750
132756 137548 134805 135816
131328 135193 132922 133637
129059 132192 130500 131437
127945 130705 129049 129615
127081 129586 128413 127932
128100 129279 129155 129643
130853 131003 130673 131102
133629 135246 134488 134815
138938 139322 138372 139610
144002 143956 143684 144399
147738 149439 148285 149038
152618 152600 152119 152458
154414 155399 154359 155374
155085 155278 153999 155287
151487 152230 152000 152519
145983 148184 146265 146959
138516 141140 138489 139866
129607 131784 131073 131287
120112 122300 121207 120955
109188 111363 110280 110101
98357 100734 99143 99586
88642 90505 89544 89774
80880 81132 80747 80458
72318 73161 72609 73247
67225 67826 67165 67794
63145 63684 63677 63377
57707 58102 58084 58129
54552 55400 54832 55116
52511 52653 52305 52510
51550 51640 51622 51663
51414 51432 51626 51116
52064 51498 51617 51840
51759 51227 51279 51691
50580 50668 50317 50467
49271 48959 49055 49183
47416 47270 47172 47487
44918 45330 44885 45230
41782 42173 42268 42198
37426 37664 37286 37679
33237 33406 33730 33344
27650 27631 27635 27875
20512 20746 20681 20729
16769 16813 16703 16987
12424 12301 12149 12249
7360 7293 7329 7270
4066 4159 4190 4082
183 208 198 186
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
