A = [
877517 903040 18081814 670068 456840 424326 409605 316359 298730 279917 281184 269461 273186 276743 275778 276121 280241 285072 284629 281966 277823 280364 276304 271754 268479 304362 302191 300214 331780 295280 298458 294492 259288 261950 260149 260263 257490 254318 253713 253602 251670 255003 252752 252584 254959 251534 248280 255352 249453 248648 249465 240393 241199 240362 234864 230568 232431 234162 228623 225135 228029 223045 221250 217849 216778 215774 211054 210082 207932 204146 202853 202480 200117 199411 199465 197519 196937 194488 192152 188789 188498 187298 183997 181560 182356 179195 175288 170919 167892 167790 164346 162773 162798 161780 160175 158825 157309 156092 155323 153923 153359 152261 150825 149433 148606 148820 147277 145374 145313 144302 143063 142371 142160 141383 140731 140813 148616 149725 149254 157108 159769 159590 159905 159524 159936 159884 158319 158262 156374 155711 154520 154139 151745 151878 151526 149770 148388 148171 146479 145837 144820 143721 142992 142031 140879 139720 138371 137980 136743 135548 133139 133314 131550 130677 129990 129108 127724 125990 124786 124634 123115 122266 120197 119060 118473 116548 116901 115628 114077 112760 111505 110958 109979 108630 107669 106742 105099 103436 102994 102589 100835 100720 99109 97757 97067 96023 94590 93857 93872 92330 91112 89845 88777 87946 86615 86249 84508 84084 82741 82056 80899 80575 78814 79029 77338 77155 75534 74652 72780 72108 71306 70802 68818 69011 67747 66444 65512 65532 64685 63743 62037 61660 60534 60297 58870 57540 56997 56532 55290 54671 53084 52424 51713 50792 50569 49499 48600 48987 47164 47012 46312 45007 45074 44270 42951 42868 41827 41725 40716 39813 39250 38719 38374 37185 37094 36352 35923 35636 34600 33775 33742 33277 32338 32354 31881 31480 30757 30021 29436 29458 28605 28514 27954 27779 26905 26413 26068 25778 25188 24860 24487 24367 23881 23381 23142 23027 22029 21838 21477 21160 20705 20160 20579 19881 19483 19428 18934 18799 18183 17851 17594 17448 17147 16841 16395 15922 16040 15650 14986 14985 14824 14843 14084 14001 14020 13663 13398 13179 13242 12983 12527 12133 12238 12016 11703 11692 11277 11396 10825 10701 10375 10507 10409 10275 10050 9865 9644 9183 9156 9114 9059 9069 8919 8487 8372 8186 8494 8311 7735 7934 7661 7517 7467 7345 7128 6918 6848 6893 6716 6620 6545 6232 6363 6341 6009 6089 5986 5986 5562 5409 5381 5378 5362 5327 5194 4987 4930 4823 4879 4614 4794 4525 4574 4500 4282 4195 4207 4239 4094 3920 4025 3651 3768 3836 3682 3695 3559 3598 3333 3458 3311 3255 3250 3193 3115 3109 2951 2803 2794 2837 2776 2848 2640 2799 2619 2577 2495 2510 2590 2362 2363 2387 2329 2322 2288 2185 2245 2132 2070 2064 2094 1915 2067 1918 1884 1780 1824 1769 1647 1814 1733 1743 1736 1640 1570 1633 1518 1623 1527 1472 1416 1543 1394 1403 1307 1365 1334 1288 1195 1275 1160 1203 1205 1204 1207 1149 1148 1140 1031 1025 1074 1071 1048 1014 1060 995 932 1004 907 925 872 845 852 905 858 829 758 869 670 738 796 736 766 771 792 691 655 650 743 636 682 644 650 650 624 624 494 547 561 586 555 553 522 569 475 517 541 481 476 505 470 473 474 434 481 446 433 420 368 415 409 431 379 389 422 322 391 365 384 317 377 305 354 335 335 357 314 299 350 321 276 275 290 283 258 275 290 251 261 313 256 267 258 281 237 276 233 222 235 219 223 216 191 242 204 257 220 209 207 217 206 177 227 178 161 171 183 165 162 176 146 159 156 157 154 137 154 170 165 143 155 127 138 125 116 124 144 127 112 118 124 125 98 131 138 155 119 131 128 95 103 106 128 112 93 114 99 128 107 85 92 115 89 99 85 93 107 91 101 89 98 123 103 95 84 61 105 89 67 92 84 78 82 92 75 86 70 76 79 61 61 64 78 63 78 63 80 54 55 65 62 52 65 48 94 73 41 57 76 69 44 48 47 56 53 49 50 61 50 36 63 41 42 33 52 54 41 48 45 52 53 51 38 38 55 48 50 47 39 34 49 35 51 38 41 41 32 27 60 34 39 36 44 40 42 26 29 40 27 37 44 33 45 26 45 47 33 47 35 27 49 30 37 29 39 33 39 30 39 29 32 37 25 26 47 30 27 47 26 27 27 18 45 30 30 34 27 23 20 39 19 23 22 22 25 26 24 34 28 26 27 25 37 34 25 20 38 15 40 32 25 30 26 20 20 27 35 28 27 48 26 34 23 21 29 33 36 28 29 19 18 32 9 23 34 28 30 30 23 12 22 18 32 29 22 23 12 22 31 27 26 18 17 20 18 20 19 18 25 32 24 17 26 15 6 22 5 16 10 13 19 19 21 22 16 14 18 15 35 16 25 19 12 20 21 14 10 26 17 8 21 12 19 15 20 6 12 10 27 11 14 18 19 23 11 12 19 15 10 20 13 17 13 5 10 20 14 10 22 11 12 14 13 8 14 13 19 12 9 16 25 18 18 9 10 8 16 8 26 10 20 13 16 11 18 16 14 11 10 11 6 9 10 6 17 17 13 12 16 14 9 8 11 17 15 10 16 13 13 7 17 19 19 15 12 7 19 9 19 15 17 16 11 17 9 13 15 6 12 12 19 12 17 12 13 7 10 16 21 10 19 20 16 8 10 8 10 12 12 8 5 8 10 8 9 19 9 10 6 10 12 8 14 14 13 14 3 9 14 9 5 8 18 4 17 9 6 11 8 11 6 3 6 10 12 7 14 10 6 4 10 10 4 7 10 8 7 12 6 10 7 6 11 7 14 6 7 15 8 7 2 4 7 10 8 6 8 8 9 13 11 14 12 5 12 10 14 5 10 6 15 11 18 4 10 9 7 9 8 8 13 5 11 10 6 16 7 9 4 14 7 7 9 13 14 10 7 21 11 15 9 8 7 16 16 15 16 9 19 16 10 11 12 20 4 222 33 19 15 17 7 11 7 10 12 5 2 11 4 5 5 7 6 6 2 2 10 3 7 4 6 4 7 6 7 5 3 7 5 8 4 6 6 7 6 6 8 16 9 6 6 6 12 9 10 9 9 8 9 4 1 4 7 5 7 6 3 3 8 7 5 3 5 4 26 1 4 6 5 4 16 7 8 11 4 9 3 6 13 8 0 6 5 2 6 7 4 6 4 5 4 2 1 13 5 13 0 6 6 5 4 3 2 1 2 0 10 0 1 5 2 4 8 3 10 1 4 2 4 7 13 6 10 5 3 6 11 5 6 2 3 5 6 3 10 5 6 8 4 5 2 3 7 8 4 9 10 6 2 3 5 5 3 2 6 7 6 2 10 8 10 9 6 1 4 7 3 14 1 5 3 4 5 6 7 3 0 7 6 4 7 6 12 2 6 6 6 10 2 6 0 8 7 13 6 3 2 2 4 4 4 5 6 8 4 10 16 5 3 7 4 5 7 5 7 3 2 7 6 23 4 8 2 1 1 3 3 4 4 0 7 9 5 0 7 4 2 2 2 5 21 4 1 2 2 1 2 2 1 3 3 4 1 4 2 4 2 3 4 0 2 0 3 4 3 0 2 2 1 5 2 0 3 0 0 1 2 1 0 6 1 1 3 2 2 2 2 1 3 3 4 4 2 0 0 5 1 0 2 2 0 2 4 3 4 2 6 4 0 3 3 0 3 1 2 1 2 1 0 0 0 2 2 3 1 6 5 1 4 0 3 0 2 1 0 3 3 0 5 1 3 4 2 0 1 0 3 0 0 0 1 2 0 0 5 3 0 1 0 0 0 0 0 0 1 1 0 0 4 0 0 0 0 1 0 2 2 1 2 2 0 3 1 2 1 2 0 2 0 0 0 0 6 0 0 3 1 2 0 1 1 7 1 1 1 8 0 2 5 4 2 3 0 1 5 6 1 13 6 0 2 2 4 6 0 0 1 2 1 0 2 0 0 0 4 0 2 2 1 0 4 0 0 0 2 1 0 0 1 0 1 1 2 1 1 1 2 3 0 4 0 5 1 4 2 1 2 1 2 3 0 2 3 0 0 3 2 1 3 3 2 2 1 1 0 0 0 0 2 3 1 0 0 1 0 0 1 0 1 2 0 0 0 0 1 0 1 2 1 0 1 0 0 0 3 4 2 1 2 1 0 0 0 2 0 2 0 0 2 1 0 0 0 0 2 6 0 0 3 2 0 0 0 1 1 0 0 0 3 0 0 1 1 1 1 1 1 3 1 2 1 1 0 0 0 2 0 0 3 0 0 1 4 0 2 0 0 0 0 2 1 1 3 0 0 2 1 0 0 1 2 1 0 1 0 2 1 0 0 0 2 0 0 0 0 0 1 3 0 1 0 0 1 0 0 0 0 0 2 0 0 1 0 1 0 2 2 1 2 0 0 1 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 2 0 0 2 1 2 0 2 0 1 0 0 0 0 3 1 0 0 0 3 0 0 2 0 1 0 1 1 0 0 0 0 0 0 5 0 0 1 1 0 0 0 2 0 0 0 0 0 1 2 0 0 1 2 0 0 0 1 0 0 0 0 0 0 2 0 1 2 0 1 0 1 0 0 0 0 0 1 0 1 4 0 3 0 1 0 1 0 0 3 0 2 0 1 0 0 2 0 1 0 1 1 2 1 5 0 2 0 1 4 2 0 1 2 2 0 1 1 4 0 0 1 0 1 2 2 1 2 6 1 1 1 0 1 2 2 1 0 0 0 1 0 6 1 2 0 1 1 2 6 3 2 1 0 2 2 1 0 1 1 3 3 3 4 4 1 2 1 2 3 1 0 6 2 0 0 1 3 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 2 0 0 0 0 0 1 1 0 0 0 2 1 0 1 2 0 1 0 0 0 0 0 0 
];
B = [
0 0 0
 156399 132454 23945
 197863 167593 30270
 203235 175202 28033
 171003 148310 22693
 104803 88426 16377
 202964 178477 24487
 118144 103124 15020
 175668 157522 18146
 211214 188845 22369
 153734 137783 15951
 282953 240536 42417
 164257 141558 22699
 76518 66096 10422
 154711 140871 13840
 139743 126111 13632
 68721 59307 9414
 170426 154983 15443
 82481 73262 9219
 56154 47258 8896
 71893 62098 9795
 55408 46505 8903
 57363 48625 8738
 246716 225809 20907
 113387 101598 11789
 81761 70794 10967
 263230 242321 20909
 128602 115287 13315
 68890 58780 10110
 336815 310418 26397
 156138 141850 14288
 82171 71536 10635
 270365 249075 21290
 141672 129297 12375
 308695 285031 23664
 134985 123628 11357
 183212 169276 13936
 496003 456759 39244
 165633 153795 11838
 304753 286785 17968
 519098 481168 37930
 209917 195009 14908
 368465 341368 27097
 453830 428101 25729
 172942 159430 13512
 426484 398233 28251
 562431 530831 31600
 218964 197680 21284
 489943 470007 19936
 1107085 1052266 54819
 91159 80384 10775
 1002735 967379 35356
 1762753 1694086 68667
 175892 157301 18591
 65934 56050 9884
 3170116 3058663 111453
 89240 74574 14666
 63151 54005 9146
 91225 76123 15102
 53900 46741 7159
 18210145 17229304 980841
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
28 37 0 0
5 5 0 0
7 25 0 0
8 20 0 1
13 4 0 0
26 11 29 0
88 59 123 11
890 20 132 16
11217 39 170 25
90668 46 238 63
257274 38 274 78
650910 100 329 136
1505650 103 538 238
3132384 174 1300 577
4945224 221 1402 780
5739878 487 1530 1236
4741490 763 2234 1971
3028110 1306 3241 3028
1575536 2052 4749 4488
673175 2898 6261 6259
212028 4031 7774 7775
45672 5813 9721 9499
13856 7921 11645 11064
13724 10407 13423 13552
15813 13587 15627 15651
18385 16757 18064 18406
20628 19823 21039 20805
23617 23239 23877 23406
26572 26556 26659 26601
29304 29437 29303 29509
31536 32617 31803 31957
34012 34456 33596 34049
35245 36526 35794 35903
36396 37652 37413 36867
39260 38756 37764 38122
38206 38396 38852 38371
37699 39639 38670 37996
37494 38366 38190 37496
37857 38540 38179 38071
37793 37886 38245 38044
38754 38460 38829 37943
39234 39438 39108 39215
40253 40399 40159 39634
41460 41165 41408 41813
43609 43460 43400 43926
45991 46362 45603 46357
48029 48368 47695 48228
49705 50133 49788 49949
51274 51930 51479 52246
53256 53294 53269 52832
53045 53439 53020 53104
52339 53229 52786 52688
51032 51496 51272 50881
49103 48950 49281 48921
46046 45907 46143 46430
42409 42623 42800 42690
38591 39078 38697 38303
34561 34939 34663 34914
31019 31450 31278 31017
27858 27852 28215 28132
24739 24965 25054 24747
22238 22459 22065 22348
20483 20619 20571 20687
19440 19635 19397 19215
18519 18740 18663 18708
18619 18267 18317 18416
18954 19107 18963 19000
25006 24887 22735 22742
20641 20552 20493 20543
21224 21326 20863 21103
19828 19809 20035 20197
17794 18148 18340 18354
18857 19041 18972 18806
13000 12948 12944 12849
10825 11031 11163 10741
8944 8839 8659 8728
7139 7168 7139 7310
6113 6177 6200 6221
5171 5141 4985 5166
4037 4125 4099 4326
2648 2661 2696 2612
1473 1432 1473 1524
81 114 87 82
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
