A = [
2594314 3034600 42468284 1272990 1292447 1251667 1032338 1121237 984666 803179 781914 724609 715782 705114 691611 688919 682110 683260 683644 670172 669444 668462 658349 656215 659878 786651 789640 810613 936753 939096 961157 968417 966749 973634 980510 979088 973559 970436 970643 962298 958529 965979 957576 955069 958960 949058 942698 951918 943564 937240 943077 929980 934222 928954 919580 916913 911283 914979 902987 899163 904801 900110 896129 896008 892195 894805 886825 881030 877998 872879 867566 863948 856991 851697 847598 839007 834294 828391 821506 814411 809953 806311 798511 791632 788700 779877 772193 761301 751030 746630 740839 733128 728837 721010 714903 712026 706418 700415 693783 688157 685223 678138 673248 669068 664719 659003 653648 648211 643346 636605 630795 628929 623224 620136 614071 610132 604366 598881 594710 588912 584293 580472 574549 571074 565078 561235 555041 551189 545963 541714 535962 531744 528226 524159 519588 515251 510796 506767 501948 497160 493493 488813 485433 480522 477221 473251 468633 464887 459257 456378 450480 448227 445207 440126 434680 431495 426728 422303 419118 414267 410787 409452 403652 400218 397401 392069 389982 385113 381798 377614 374318 371677 365953 364586 359567 357589 353035 350674 347357 343726 340679 336461 334127 331052 328406 324929 321656 318692 315259 315034 310035 306607 303354 300946 298686 295034 292452 289289 286639 283816 280187 278623 275197 272587 269315 266516 264343 261305 258691 256453 254316 250390 248745 245233 243108 240848 238125 235058 234115 230784 228917 227029 223661 221845 218940 215885 214496 213343 210234 208412 205996 202407 201279 198168 196473 194379 191996 189994 187968 186040 184187 181805 180282 178847 176479 174126 172017 171001 168852 166177 164679 163217 160581 159350 157931 155386 153517 151999 150085 148397 146994 144954 143692 141731 140163 138267 136788 134772 133664 132137 130062 128991 126907 125938 124459 122788 121331 119766 118393 116981 115901 113868 112947 111814 110235 108388 107774 106632 104462 103227 102394 101671 100027 98538 97604 96235 94609 93815 92915 91862 90504 88930 88544 87249 85954 84769 83618 82904 81941 80551 79719 78853 77866 76753 75401 74900 73846 72754 72187 71682 70150 69300 68451 67481 66699 66146 65080 63932 63246 62599 61717 60953 60050 59421 58545 58215 57141 56507 55880 55246 54481 53364 53360 52167 51553 51023 49697 49339 48815 47846 47306 46913 45883 45695 45256 44684 44275 43026 42859 42253 41656 40942 40747 40138 39250 39104 38710 37525 37398 36852 36285 36002 35555 34934 34760 34220 33647 33392 32762 32093 31853 31462 31153 30230 30248 29726 29081 28918 28784 28242 27534 27368 27231 26841 26313 25788 25818 24978 24769 24396 24402 23747 23359 23007 22885 22513 22322 22054 21584 21512 21096 20924 20761 20098 19877 19580 19512 18975 18887 18581 18433 18186 17662 17742 17424 17074 16862 16488 16323 16057 16122 15728 15520 15239 15306 14788 14699 14245 14441 14041 13786 13438 13671 13306 12957 13091 12721 12669 12353 12116 12013 11980 11645 11718 11517 11483 11216 11027 10899 10519 10487 10174 10196 10048 9675 9647 9677 9499 9415 9394 9140 8950 8804 8861 8579 8548 8400 8235 8087 8164 7878 7716 7652 7603 7670 7368 7385 7209 7043 6975 6947 6846 6739 6656 6651 6549 6266 6428 6202 6179 5982 5988 5837 5833 5578 5500 5435 5461 5259 5405 5356 5202 5041 5056 5017 4995 5058 4681 4753 4593 4594 4513 4434 4514 4411 4248 4231 4199 4144 3913 4031 3995 3929 3849 3925 3773 3761 3664 3549 3579 3580 3541 3437 3395 3396 3336 3191 3313 3188 3156 3205 3041 3021 3075 2963 2880 2922 2822 2809 2839 2791 2750 2700 2659 2585 2714 2542 2547 2482 2510 2406 2296 2312 2333 2266 2221 2297 2250 2259 2254 2239 2147 2187 2069 2106 2030 2003 2036 2000 1965 2001 1851 1932 1994 1914 1848 1857 1791 1750 1635 1726 1736 1733 1731 1650 1654 1684 1719 1664 1649 1573 1533 1621 1499 1498 1576 1509 1404 1506 1437 1431 1471 1411 1429 1375 1381 1366 1403 1344 1287 1373 1333 1301 1317 1290 1204 1258 1191 1235 1203 1141 1234 1199 1218 1121 1157 1213 1148 1190 1162 1061 1078 1140 1086 1102 1105 1105 1030 1064 1098 1045 1083 1004 1001 994 1007 968 963 964 940 982 975 921 944 955 916 849 889 884 872 926 927 866 873 845 791 861 828 892 828 852 801 774 771 797 782 782 776 749 772 707 723 781 800 774 738 786 777 745 795 727 725 765 680 696 714 688 684 682 672 674 664 725 684 672 616 676 664 654 629 637 625 629 646 667 647 617 668 625 639 600 627 595 630 583 631 622 592 595 605 595 582 549 571 589 559 588 505 527 531 565 551 510 537 504 526 529 510 524 483 517 493 498 529 497 533 518 494 503 485 468 508 487 496 483 468 482 490 442 473 486 505 475 501 517 484 445 440 408 466 477 444 424 438 459 453 446 431 427 433 433 435 463 436 437 458 396 443 390 402 443 416 440 380 410 409 394 453 420 391 375 384 395 400 365 376 357 406 360 356 389 352 367 323 346 372 358 342 319 379 369 328 356 355 337 378 336 325 351 339 328 362 312 360 351 330 319 320 349 340 309 348 304 304 349 313 297 345 299 298 313 287 310 296 313 307 301 293 297 287 285 299 312 270 287 282 304 274 262 276 305 289 276 271 288 282 301 284 275 260 240 296 282 274 271 250 270 240 281 289 241 267 251 264 278 234 265 240 273 246 252 242 268 224 281 240 253 236 232 235 242 271 228 229 252 242 225 245 242 246 257 236 260 248 255 217 257 245 231 219 227 224 257 212 241 226 218 231 230 195 216 218 182 210 235 203 210 231 216 192 208 218 200 185 215 202 186 174 196 189 207 187 193 175 196 200 210 197 174 208 200 177 187 209 189 191 172 192 176 185 167 167 162 192 164 155 158 152 158 179 156 162 161 175 151 155 149 181 156 192 144 167 172 141 167 153 173 152 149 146 156 142 161 169 151 150 166 145 142 150 167 141 169 128 144 146 152 123 154 153 138 149 161 150 132 161 145 135 120 129 147 146 135 145 121 119 138 133 126 130 149 127 126 127 137 123 138 129 131 110 133 129 116 116 99 132 101 136 128 96 100 124 104 132 101 116 132 142 131 111 99 115 136 104 119 101 117 135 102 113 113 115 127 135 104 111 110 107 108 104 113 109 114 91 99 95 112 116 90 96 113 96 108 105 93 87 106 100 98 99 95 96 96 86 116 86 96 118 97 101 82 86 115 111 146 137 152 148 142 170 155 140 161 158 132 139 127 95 126 91 72 91 100 94 83 80 69 70 74 79 105 78 80 77 76 92 81 72 88 75 81 84 76 71 86 97 82 88 78 87 89 76 73 77 72 81 92 69 74 70 68 72 60 58 63 65 70 64 65 64 62 76 75 61 71 74 88 93 60 77 72 74 68 71 78 76 63 64 61 59 61 56 78 79 73 55 50 51 77 55 57 75 74 62 63 59 60 64 60 70 69 70 59 62 66 56 61 43 119 76 68 72 67 47 52 69 44 38 56 59 46 59 42 58 47 47 59 59 69 48 63 47 49 54 47 53 43 60 41 45 46 51 49 42 49 46 37 52 48 46 44 48 46 53 57 41 44 30 46 46 36 49 48 53 42 41 50 41 34 38 49 59 59 40 45 45 39 49 36 32 45 35 40 47 31 47 40 44 43 52 39 36 48 35 29 42 45 51 42 45 35 43 47 35 39 32 36 31 39 44 43 33 32 34 39 40 36 42 32 21 47 31 27 31 33 34 28 38 35 30 38 31 37 38 46 44 34 32 36 38 26 25 31 34 24 36 32 26 24 21 33 35 33 28 28 25 23 30 41 30 25 35 31 36 30 35 28 23 30 25 27 31 25 28 25 21 25 35 18 31 29 23 26 23 18 25 29 15 30 33 37 25 31 23 34 26 29 29 27 29 18 20 20 26 32 25 19 25 24 35 24 24 23 23 17 28 29 38 29 26 36 40 41 31 36 27 33 25 26 31 19 25 27 24 26 17 28 27 22 23 23 29 25 29 22 25 29 26 30 28 24 22 16 25 31 18 27 32 29 24 23 30 25 33 34 22 20 25 20 25 22 23 21 32 19 18 31 32 33 25 23 18 21 14 21 21 24 27 17 13 21 25 24 18 19 18 25 18 15 16 21 16 20 9 19 12 15 22 19 22 24 16 21 20 19 14 23 22 19 16 12 19 9 18 16 19 24 15 24 14 15 17 12 13 16 25 18 14 9 19 12 14 13 16 15 26 12 15 14 16 20 24 13 17 16 27 14 17 11 13 18 19 13 11 14 16 21 18 18 8 17 13 17 20 13 19 15 10 18 18 17 11 15 16 12 12 14 16 15 8 15 13 13 12 19 19 17 17 19 9 10 17 13 11 16 9 19 17 14 8 9 13 20 12 17 16 9 9 9 4 10 14 18 10 5 19 12 8 11 10 8 15 15 16 15 17 16 17 8 12 15 10 10 11 13 11 13 9 17 13 11 14 7 11 14 7 15 10 14 8 9 6 11 10 9 14 8 10 7 7 11 9 10 4 10 14 6 11 13 9 9 16 11 9 9 15 14 13 13 10 15 14 12 8 6 6 7 9 12 9 12 12 9 12 5 10 6 16 8 14 9 11 10 6 8 11 9 4 7 15 12 12 11 9 9 4 9 8 11 10 6 11 11 13 8 11 7 3 5 12 4 10 8 8 4 5 11 10 5 11 8 15 5 4 9 5 9 5 6 5 14 18 2 5 6 10 6 8 6 8 7 10 13 6 12 8 8 9 12 4 6 9 7 12 7 7 9 13 10 10 6 8 6 8 5 4 9 14 7 10 3 10 13 7 12 10 10 8 5 6 4 6 6 6 6 3 3 6 5 6 13 3 10 4 6 15 10 11 8 4 9 6 7 12 5 8 1 9 12 7 3 10 4 7 7 3 5 6 9 8 10 9 8 10 10 8 8 9 11 14 10 12 10 5 12 7 11 8 4 7 3 5 8 8 3 9 7 8 3 2 2 7 5 6 2 6 4 2 6 5 7 6 3 3 8 5 4 9 2 3 3 4 6 7 3 7 4 7 9 9 4 5 5 5 2 7 5 10 1 7 7 6 14 4 3 3 4 8 2 4 
];
B = [
0 0 0
 1055439 851431 204008
 589651 471490 118161
 1144581 945597 198984
 1020653 839253 181400
 631877 519755 112122
 1157817 971728 186089
 1024238 859158 165080
 708840 596630 112210
 1347453 1140298 207155
 1227264 1029869 197395
 718599 607639 110960
 2184824 1839100 345724
 599178 512479 86699
 384631 332148 52483
 1209187 1050650 158537
 401971 346639 55332
 315408 274823 40585
 1276833 1113101 163732
 81426 69054 12372
 71243 61834 9409
 20843 18154 2689
 7655 6712 943
 409393 357936 51457
 2061139 1797241 263898
 121246 104611 16635
 505768 443913 61855
 2177493 1904950 272543
 137780 122074 15706
 780339 682274 98065
 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 = [
235 755 1 1
29 106 0 0
81 119 0 1
111 154 0 0
74 167 2 1
101 156 1010 52
2387 217 2828 268
29799 223 3824 706
134384 296 5062 1044
423576 322 6890 1706
893887 389 8306 2319
1804499 528 10717 3659
3149861 785 12422 5019
5237617 1407 14961 6979
7637851 2241 17187 9275
10353320 3806 19467 12513
12116125 5785 21740 16243
12041798 8691 24295 21248
9460327 12691 28570 27531
5198609 17544 34905 34637
1780372 23495 42136 42229
330052 31316 50639 50692
74742 42701 59671 59281
70841 55525 69087 69142
80068 69525 80091 80690
91246 84615 91574 92383
103593 100121 104885 105447
116169 116524 118225 118743
128646 130837 131430 132771
142059 144032 143976 145665
152834 157747 155723 157191
163677 167101 165284 166354
169480 175659 172825 174803
174799 182032 178451 179435
177527 185550 181297 181747
178978 185595 181578 182588
176988 183956 179788 181232
174862 179707 177267 177546
172248 176159 173783 175008
170620 173964 171528 172089
169295 172298 170953 170258
170706 171687 171647 172382
173410 174194 173955 174952
177669 179305 178710 178836
184288 184513 183329 185260
190880 191097 190429 191648
195801 197916 196511 197025
201423 201772 201063 201953
203965 205209 203877 205240
204906 205230 203357 205136
199872 201130 200884 201346
193024 195650 193453 194195
182467 186322 183480 184338
171076 174125 172924 173479
158479 161487 159670 160003
144222 147526 145735 145575
130171 133302 131274 131510
117836 120201 118720 118685
107460 108277 107147 107355
96444 97304 97153 97823
90109 90908 89895 90695
85031 85563 85603 85172
78076 78459 78298 78529
73627 74488 73962 74512
70847 71076 70704 71172
69639 70108 69876 70094
69473 69487 69614 68967
70717 70167 70164 70364
69790 69368 69547 69600
68242 68094 68028 68045
66236 66003 66244 66275
64365 63994 63954 64581
61174 61598 61064 61489
57007 57283 57487 57352
50937 51301 50962 51386
45711 45758 45949 45513
37942 38078 37868 38002
28384 28519 28402 28459
22810 22786 22594 23078
16976 16733 16616 16742
9874 9807 9817 9775
5565 5763 5765 5693
253 304 295 277
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
