A = [
539755 543065 2614789 588517 575050 547400 528857 554941 540755 570085 641317 773921 986150 1188620 1344665 1465224 1643219 1817027 1823630 1795123 1882864 1933580 1891711 1851590 1862184 1971887 1913484 1823782 1836452 1408712 1344478 1237226 774748 775708 764829 762133 754277 734024 735091 740001 728169 732364 735714 731459 743864 730117 722074 745128 720626 718988 716803 683492 697296 698009 682078 659833 671004 685698 651005 634481 646549 632397 622337 611953 603720 600899 586042 574800 569958 556565 551053 550460 540973 540452 543766 535033 530317 529524 514852 506101 499355 495333 483478 476799 477125 462569 450599 431343 420308 414876 407903 400508 396828 392053 384309 381310 375823 372178 365892 359515 356334 349902 341960 337968 333662 330342 326458 321557 316406 313557 307409 306612 301766 297987 296670 293415 358603 361434 358573 423432 428642 425293 419360 413762 407001 400850 395031 389426 381153 376132 368244 361727 353863 348519 343261 336476 331378 326590 319247 315200 308182 304504 299023 294481 287865 282859 278210 272530 268011 264250 259634 254651 250139 245328 239788 235679 230960 226513 222035 219795 215764 211437 206485 203734 199674 195506 192852 189558 186301 183957 179633 177125 174168 171390 168637 165175 162161 160732 157244 154970 151174 148880 146914 144915 142418 140546 137407 134734 134028 131279 130357 126607 125629 123431 121198 119177 117572 115940 114574 112531 110940 109348 107556 105415 104610 102821 100952 99285 97176 96239 94414 92785 90860 89082 88576 87730 85780 84706 83846 81796 80953 78978 77969 77331 75421 73721 71669 70138 68633 67408 65703 64786 63271 62266 60870 59565 59205 57367 56433 55592 54847 53605 52450 52686 51046 50401 48895 48236 47408 46983 46195 45486 44632 43614 43067 42194 41763 40952 40146 39686 39256 38354 38002 37060 37004 36072 35777 34610 34023 33579 33454 32577 31769 31640 31609 31056 30185 29629 29037 28747 28068 27644 27236 27125 26845 26132 25713 24978 25069 24646 24077 23771 22982 23085 22604 22615 21740 21902 21443 20895 20673 20344 19752 19894 18974 18973 18982 18065 18277 17392 17186 17041 17151 16632 16668 16308 15824 15500 15563 15525 14946 14933 14127 14443 13939 14023 13702 13255 13100 12853 12757 12788 12352 11991 11849 11763 11604 11406 11298 11106 10770 10669 10517 10282 10277 9750 9846 9590 9408 9452 9270 9246 9164 8836 8629 8551 8453 8291 8083 8292 7860 7828 7696 7461 7299 7273 7233 6958 6970 6803 6790 6905 6350 6437 6431 6325 6121 5797 5876 5858 5856 5608 5645 5446 5425 5130 5104 5174 4995 4965 4981 4767 4792 4676 4499 4442 4466 4181 4220 4171 4191 4061 4043 3726 3997 3834 3642 3611 3648 3613 3510 3393 3303 3529 3303 3171 3156 3170 2915 3034 3014 2928 2900 2803 2868 2688 2791 2706 2577 2657 2435 2458 2487 2541 2430 2325 2377 2278 2267 2145 2214 2093 2074 2064 2069 2076 1908 1978 1877 1788 1875 1859 1812 1747 1636 1683 1747 1671 1638 1555 1542 1560 1482 1614 1520 1471 1502 1345 1363 1360 1428 1267 1354 1287 1305 1259 1252 1227 1175 1218 1204 1139 1081 1170 1061 1064 1057 1000 930 1026 993 941 946 915 940 913 871 856 814 892 826 883 813 787 798 763 805 757 737 748 713 738 700 705 678 683 641 674 608 638 600 574 570 599 586 561 532 556 501 513 516 538 478 461 584 508 444 456 470 440 468 445 386 466 430 373 407 431 352 410 340 444 390 387 396 332 368 365 348 341 340 311 303 348 319 336 305 283 300 286 280 321 301 272 210 283 281 277 240 259 244 263 221 266 262 219 245 248 222 212 226 237 218 230 216 205 236 189 222 184 211 186 187 179 140 177 219 181 190 191 167 174 157 173 167 156 166 158 188 177 161 157 170 175 128 147 134 144 154 132 145 148 141 153 124 106 128 151 122 124 120 153 138 143 138 105 112 117 126 79 118 118 114 99 95 127 116 121 121 103 109 87 109 85 116 88 108 113 83 88 88 89 100 102 76 79 101 73 106 79 88 93 75 92 81 82 85 95 69 95 93 55 73 80 77 64 67 75 77 80 89 70 76 65 56 93 77 85 63 78 93 75 47 66 76 63 70 58 50 67 57 51 49 48 68 56 58 49 66 64 80 50 76 75 80 71 66 53 61 54 55 45 39 66 51 59 46 71 41 55 49 39 48 48 37 54 43 39 50 43 43 36 50 48 54 50 42 43 36 45 31 42 42 56 46 40 41 44 40 36 57 51 42 47 32 27 41 27 44 28 43 51 48 43 38 18 36 32 36 45 31 27 39 53 40 46 42 44 35 35 47 32 49 27 34 38 43 40 32 38 19 33 54 37 33 34 32 35 38 40 30 32 37 28 29 28 23 30 24 17 33 26 29 27 26 27 26 29 26 42 36 28 28 33 26 27 26 29 37 28 21 35 30 25 18 26 33 31 25 25 18 22 16 34 20 24 19 22 14 24 24 29 26 32 15 22 22 26 25 24 25 26 12 17 20 27 14 29 14 18 21 17 26 33 20 25 22 19 31 21 13 23 23 22 28 24 17 25 13 23 10 28 19 22 22 18 22 28 21 19 22 13 20 25 26 19 13 14 18 17 31 9 25 14 14 16 20 13 14 7 19 17 10 9 25 21 16 12 21 15 19 18 23 7 25 7 15 12 16 19 24 20 14 19 19 12 11 9 11 17 14 15 6 26 12 22 16 6 13 11 21 10 13 15 10 20 6 20 8 8 21 6 14 10 12 16 13 13 20 13 17 16 11 18 12 11 26 9 11 11 15 11 17 9 21 16 28 12 28 11 4 18 9 5 9 13 4 14 12 5 21 12 11 3 11 16 10 8 8 17 13 7 23 10 14 24 20 23 17 16 19 10 20 20 24 18 15 22 11 27 14 14 23 19 19 13 11 15 19 15 21 15 18 21 16 22 27 12 10 25 21 23 23 18 16 17 21 13 32 20 18 17 26 30 16 35 30 29 39 27 41 37 33 39 36 577 69 50 48 43 20 34 28 9 12 9 19 10 11 18 17 13 8 10 16 14 13 14 7 9 11 11 9 10 9 13 7 15 5 9 2 9 13 6 12 8 8 15 6 16 42 23 39 50 37 37 64 32 6 10 11 8 3 16 16 8 8 8 9 6 5 13 13 9 54 12 4 4 7 7 6 4 5 10 12 8 4 6 4 6 5 8 5 1 4 6 8 8 10 4 11 7 4 5 3 5 5 14 3 9 6 12 4 8 2 8 12 5 6 6 6 4 11 15 14 13 9 17 8 13 10 5 15 10 19 7 15 13 18 9 9 8 11 10 11 11 14 16 12 10 13 15 10 20 17 15 14 15 24 25 14 12 13 19 14 16 9 12 16 14 12 15 13 10 10 13 19 10 8 5 10 14 14 15 16 10 6 7 10 15 15 12 17 8 20 19 20 6 17 11 11 13 17 11 10 15 14 12 18 10 10 12 12 13 14 13 11 3 5 9 9 6 4 7 3 8 8 4 8 7 5 4 6 4 8 4 4 6 4 5 4 6 6 4 3 8 4 2 9 2 5 3 6 1 5 5 5 1 4 3 0 0 7 3 4 3 2 7 1 1 4 3 5 4 3 6 1 4 1 1 5 4 5 4 8 5 8 8 3 4 5 5 6 0 1 4 5 3 6 8 3 2 2 4 5 0 4 2 6 9 5 4 3 3 9 4 2 8 6 7 5 3 5 5 4 1 3 1 4 0 4 1 5 3 7 11 4 3 5 13 8 4 4 6 1 3 0 5 4 1 3 6 6 5 5 3 4 7 4 6 10 1 5 3 6 7 6 6 3 2 8 2 7 4 6 12 2 2 5 3 13 2 1 5 5 1 7 6 9 4 4 5 5 8 4 4 12 7 2 1 10 6 2 5 7 8 3 5 5 8 6 8 3 6 8 7 4 3 10 3 5 5 4 4 7 2 0 4 12 6 5 4 5 3 16 10 16 6 8 8 9 4 1 18 7 9 8 10 12 18 13 13 14 9 22 3 7 8 9 14 4 11 6 9 14 14 11 17 2 16 5 6 7 15 14 7 3 8 19 10 14 11 4 8 3 3 8 3 2 6 7 5 3 2 3 7 3 1 4 4 5 1 4 3 1 2 4 1 6 4 8 1 4 1 1 2 3 5 7 0 4 7 8 4 2 5 5 10 3 9 7 8 8 1 6 5 2 2 4 3 4 0 7 3 4 1 4 5 0 1 4 2 1 2 5 7 1 1 2 6 6 3 4 3 0 3 1 2 3 2 0 2 3 1 2 1 1 3 0 0 0 4 0 4 0 3 1 6 1 0 4 1 1 3 6 1 2 0 3 1 0 4 0 1 3 1 2 0 3 1 1 3 1 2 0 0 2 0 2 2 2 2 4 3 4 3 0 2 0 1 2 5 3 3 1 0 2 4 0 1 2 1 0 1 2 1 0 0 0 5 2 0 2 0 1 2 1 1 0 1 1 0 2 1 0 3 1 2 1 1 0 1 0 2 1 0 1 0 0 0 0 1 2 2 1 1 7 3 3 2 5 0 0 1 2 2 1 3 2 2 0 0 2 0 0 0 1 0 0 4 3 0 3 2 0 2 3 0 0 2 2 4 1 1 2 0 3 0 0 1 0 2 2 2 1 1 1 1 2 0 0 0 1 1 1 0 1 0 3 0 3 1 0 0 1 0 1 1 1 2 2 1 0 3 1 2 1 0 1 1 3 4 1 2 0 0 5 3 0 4 0 0 4 4 6 2 4 1 3 2 0 1 1 7 1 4 3 2 1 1 2 3 0 4 2 3 1 1 1 0 4 1 1 0 2 3 2 0 1 0 2 3 5 0 0 1 1 3 2 0 2 2 1 1 3 0 0 3 2 1 2 3 3 4 2 2 3 0 8 5 0 3 0 1 1 1 0 0 3 0 0 0 1 3 3 1 0 4 0 0 0 1 0 3 1 0 2 0 3 0 0 1 0 0 1 0 3 4 3 1 
];
B = [
0 0 0
 290116 208048 82068
 442319 332832 109487
 386832 302100 84732
 320088 247654 72434
 277654 215815 61839
 216961 172638 44323
 187334 151226 36108
 173469 138989 34480
 195083 150434 44649
 285056 221162 63894
 244303 191429 52874
 238283 188634 49649
 224516 176521 47995
 213983 169034 44949
 257861 206304 51557
 238680 192123 46557
 257413 210592 46821
 233367 190441 42926
 246127 200836 45291
 275853 225088 50765
 262916 214868 48048
 269698 222484 47214
 268980 222261 46719
 258147 212555 45592
 289591 238320 51271
 253858 208249 45609
 289617 238788 50829
 259112 215029 44083
 276798 229846 46952
 279456 230464 48992
 285506 236658 48848
 275665 229090 46575
 266033 220729 45304
 327468 272503 54965
 271889 225934 45955
 274068 228131 45937
 645627 535375 110252
 261291 218007 43284
 310745 259634 51111
 534754 445443 89311
 296485 247966 48519
 480690 401656 79034
 256049 214168 41881
 296341 248928 47413
 488424 409432 78992
 298592 251342 47250
 468308 393917 74391
 291790 245459 46331
 457534 385889 71645
 291076 246077 44999
 452688 382374 70314
 305206 259114 46092
 449404 380958 68446
 288590 245322 43268
 480125 409414 70711
 422867 360804 62063
 269751 230276 39475
 427457 365676 61781
 215367 184678 30689
 39766648 36814529 2952119
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
3 11 0 0
3 2 0 0
2 4 0 0
6 6 0 0
4 6 0 0
7 6 0 0
7 20 0 0
11 9 1 1
82078 11 1 0
1009279 30 1 0
2197143 18 3 2
3860029 35 18 2
5386037 63 135 49
6225410 125 518 173
5544372 205 755 534
4229208 497 1909 1791
2636755 1128 4436 4387
1507395 2123 7916 7580
826266 3708 12055 11773
364946 6012 15925 16432
123139 8751 20715 20684
43804 13076 25366 25819
34116 18770 30435 30890
38863 25929 36342 36247
45486 34417 43046 42858
53083 43488 50377 50294
61138 52939 57929 58027
68708 61367 65304 64915
75233 69710 72791 72978
81055 76264 79218 78784
85757 81184 83230 84339
88884 85115 85395 87228
89334 87083 88717 88773
90772 88995 89412 89681
94786 89113 89926 90374
92354 90249 90538 90395
90747 90693 89734 90468
90542 90600 90850 91161
92126 90954 91580 92940
93127 92519 93217 93061
94723 94498 94332 95149
97099 96087 95359 96969
99396 99589 99335 99715
103119 102504 102907 103355
107799 107298 107102 107644
112766 111648 111986 112225
116141 116206 116089 116143
120387 120009 120574 121047
124592 123961 123917 124756
127737 127253 127130 127724
129209 129315 128554 128972
130218 130329 129266 130240
127969 127465 127394 129406
124859 125813 124836 125234
119299 120746 119664 121288
113275 113946 113531 114386
107441 107749 108050 108263
99539 99484 98968 99849
90639 90878 89848 91206
82633 82249 82322 83208
74566 74503 74132 74802
67905 68274 67332 68189
61403 60825 60823 61600
56347 56354 55391 56424
53201 53282 53223 53517
50890 51304 51356 51298
51155 51321 50894 51214
53706 54353 51261 51548
48860 48345 47969 48242
48936 49218 48833 49091
47775 48196 47408 47896
45621 45271 45727 45865
43098 42990 43127 43509
37101 37681 37119 36807
31419 31202 31609 32004
26133 26244 26015 25828
19786 19996 19636 19729
13010 12950 12792 13051
9792 9923 9881 9918
7267 7406 7383 7335
4205 4259 4102 4172
2053 2092 2043 2018
94 120 100 107
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
