A = [
313436 310334 1620788 255467 247409 232656 221211 218546 212637 201080 197873 194698 190869 187693 184622 181912 179766 177507 175493 173673 173023 170372 169663 169341 172130 233097 232175 235125 295858 295417 300413 302461 303990 307964 309836 306978 302937 301059 298190 294341 294423 292145 291617 291016 291014 287774 285371 281990 279134 277872 275180 274243 272253 272357 271588 269167 268236 264798 263475 259758 259421 257157 255623 254388 252039 251763 250301 248355 246243 243581 241674 240746 238044 236107 234347 233770 232397 230072 227840 225947 224117 222270 220885 219431 217735 215997 214549 213343 210538 209732 206774 205392 203722 202718 200615 200546 197570 196849 195061 192803 192035 190372 187524 186656 186310 184046 183506 183029 179921 179823 176717 174826 173389 172135 171238 168599 167803 166601 165761 163856 162784 160323 158645 156350 154930 154633 153108 152297 150990 149055 147759 147151 145708 144733 143270 141843 140658 138668 137945 136478 136026 133886 133231 132044 130719 129959 128400 127272 126169 125108 124641 122902 121101 120303 119331 118280 117449 115958 114420 114066 112597 111748 109200 108567 107354 106056 105757 105045 103932 102720 101641 100075 99136 97924 97577 96511 94904 94389 93567 92349 92268 90591 89721 89448 88274 87273 86635 85384 84455 83597 83034 82466 80919 79862 79757 78372 77941 76420 76426 75202 74181 73299 72656 71603 70989 70231 68921 67994 67750 66720 66272 65639 64835 64117 63114 63053 62694 60954 60487 59825 59057 58249 58065 56967 55963 55549 54973 54138 53656 52704 52378 51582 50912 50087 49358 49172 48311 47858 46998 45867 46573 45354 44866 44449 44034 43463 43422 42600 42196 41504 40659 40473 39875 39405 39043 38361 37807 37486 36612 36476 36002 35556 35258 34548 34147 33524 33025 32350 32320 31673 31429 30814 30460 30324 29956 29159 29115 28798 28186 28007 27455 27036 26750 26962 26423 26187 25441 25337 25349 24417 23989 23844 23334 23052 22903 22905 22274 21885 21620 21548 21113 20566 20664 20845 20341 19810 19872 19346 19232 18744 18509 18145 18180 17699 17793 17224 17012 16441 16353 16091 16205 15530 15177 15032 14620 14771 14349 13843 13790 13652 13381 13239 13019 12695 12781 12189 12181 12302 12077 12165 12132 11819 11452 11663 11277 10975 10847 10554 10533 10379 10236 11109 9974 9836 10114 9701 10932 9412 9196 9257 9023 8919 8813 8721 8399 8467 8156 8122 7813 7935 7759 7640 7474 7329 7263 7177 7196 7015 6802 6753 6660 6657 6379 6322 6641 6352 6140 6188 6245 6065 6038 5973 6089 5849 5851 5783 5412 5295 5210 5002 4993 5008 4878 4883 4828 4876 4783 4688 4430 4512 4314 4202 4252 4133 4123 4079 3974 3894 3940 3707 3720 3621 3668 3680 3582 3483 3521 3408 3415 3421 3239 3122 3253 3130 3153 3161 3075 2895 3045 2802 2810 2695 2687 2660 2588 2645 2572 2482 2502 2487 2381 2497 2390 2464 2329 2295 2282 2215 2160 2134 2080 2092 2107 2070 2038 2046 1964 2056 1953 1932 1995 1897 1907 1838 1768 1768 1734 1814 1706 1687 1663 1672 1644 1670 1602 1675 1614 1561 1538 1469 1543 1528 1464 1485 1456 1448 1401 1361 1371 1337 1309 1356 1302 1320 1385 1329 1325 1285 1259 1275 1138 1239 1161 1199 1220 1128 1167 1141 1113 1095 1073 1036 1063 1059 1029 1032 1046 996 1029 1077 1022 1059 962 1005 984 957 1015 1021 945 1038 948 953 946 978 983 965 953 1021 953 945 948 857 882 858 843 809 871 942 871 891 796 851 821 848 846 710 717 713 753 693 748 701 793 807 789 810 815 728 740 712 697 730 599 714 693 613 662 648 673 642 627 634 655 695 675 613 626 595 645 640 563 555 550 564 534 567 539 540 545 544 541 504 483 492 497 444 471 451 502 489 448 426 498 467 448 435 405 457 443 477 398 436 434 438 414 415 428 445 408 413 415 431 427 412 384 402 366 409 322 382 375 375 401 412 380 404 411 385 337 355 315 361 355 364 401 363 333 371 386 319 342 314 356 314 338 347 317 307 277 301 290 294 292 329 311 332 287 319 309 285 307 335 307 285 298 291 288 301 278 276 283 306 294 288 305 285 286 309 301 296 273 282 275 264 269 259 273 306 283 288 294 309 292 264 280 265 263 274 308 259 283 331 294 320 372 437 438 384 404 412 316 342 360 415 337 315 429 358 362 321 336 396 318 318 262 271 284 284 243 220 231 250 206 188 227 221 235 248 224 245 277 284 248 297 267 245 249 249 226 238 246 237 255 236 234 226 235 282 231 198 189 212 211 193 193 182 229 208 217 189 240 204 212 224 241 192 176 192 248 189 199 181 162 217 181 180 186 168 195 183 185 193 194 150 146 203 189 202 173 193 168 171 203 182 200 174 181 197 182 150 194 207 188 172 162 171 183 202 165 166 175 175 178 168 148 186 167 157 155 125 158 120 130 135 120 124 142 132 176 126 135 137 132 166 134 142 148 157 152 169 151 174 173 158 152 135 134 120 139 121 126 145 149 116 127 138 159 114 146 118 103 120 104 120 121 122 124 131 148 105 106 117 122 96 138 145 121 131 131 148 264 136 117 117 124 104 100 123 115 109 104 124 96 99 137 85 104 101 102 92 92 83 83 97 82 86 92 109 96 93 89 105 78 90 106 87 89 90 94 96 67 86 72 77 92 81 75 62 82 85 61 56 70 75 60 79 73 77 85 74 96 90 71 70 98 92 68 69 69 97 71 83 74 92 71 79 79 75 85 89 70 96 67 84 69 68 74 80 85 65 55 74 79 74 78 60 54 63 68 52 56 63 70 69 54 68 75 59 60 70 81 76 58 50 67 72 60 56 45 56 67 64 49 54 52 64 75 60 76 65 72 71 58 58 58 65 73 75 70 71 62 72 69 61 61 76 61 53 65 58 56 52 66 71 67 58 81 56 49 73 56 56 52 53 71 62 48 65 53 60 49 73 57 55 65 72 54 68 54 52 53 45 63 53 42 46 48 44 41 49 56 62 47 43 46 63 49 38 52 38 56 54 54 51 64 60 37 63 40 45 45 63 58 56 53 56 38 47 54 54 36 43 43 44 36 45 43 45 40 47 34 34 39 39 53 51 38 58 43 43 48 54 50 40 63 35 59 50 49 48 58 47 49 41 43 55 60 47 43 52 55 49 51 50 47 54 47 49 44 43 39 38 46 42 49 41 46 37 50 37 38 33 49 36 35 26 34 36 34 35 24 35 26 27 30 28 30 36 31 38 25 39 32 26 35 28 32 25 25 15 27 31 30 25 18 22 22 28 24 27 27 30 25 34 33 36 37 31 24 30 24 30 30 26 33 30 25 31 20 34 28 26 21 28 25 22 25 22 38 27 32 22 29 21 31 37 30 23 26 29 32 30 25 31 36 26 32 23 21 27 19 31 25 26 26 27 36 25 28 31 32 31 22 25 21 26 18 29 27 14 22 19 19 16 15 24 32 16 29 26 29 24 18 13 23 16 18 8 17 18 17 14 15 11 18 17 15 12 12 19 14 21 22 22 20 21 22 19 20 13 23 17 16 19 25 17 14 15 16 13 22 15 13 19 27 13 13 24 13 17 12 11 11 10 20 15 20 10 22 9 22 12 10 12 18 15 17 13 24 16 18 13 18 13 12 27 22 18 23 11 16 22 16 18 18 22 20 24 29 19 41 18 29 24 26 26 37 23 31 30 22 20 24 30 22 20 19 24 18 23 18 23 24 27 19 21 19 30 18 24 19 27 32 25 21 31 14 15 22 31 19 16 24 17 16 15 16 13 16 17 11 13 14 17 19 16 24 11 14 6 16 14 14 11 16 9 9 16 11 10 19 13 12 13 8 10 10 12 7 21 8 6 7 13 10 12 11 15 10 10 7 9 12 19 13 19 11 12 20 19 14 12 8 13 13 7 10 8 7 13 6 19 8 10 17 18 5 8 9 6 8 13 13 10 6 14 15 11 15 10 15 9 4 13 7 9 9 11 8 14 8 7 4 9 8 5 7 8 11 9 9 10 9 6 10 4 14 14 9 13 12 6 9 6 6 13 6 7 6 8 8 6 7 7 8 10 6 7 9 9 7 11 6 13 5 12 13 11 16 13 14 14 11 15 12 12 9 9 14 12 12 15 9 9 10 18 17 6 10 14 25 18 6 7 5 10 12 9 10 14 13 11 10 21 18 17 20 15 20 19 11 18 23 4 7 8 9 5 6 12 8 5 7 7 8 9 17 8 6 2 8 8 11 13 11 8 7 8 10 9 9 5 7 15 6 9 8 49 68 61 79 80 56 63 70 23 10 6 4 7 9 12 9 8 4 3 7 10 1 6 9 8 8 5 12 3 15 5 11 10 4 7 16 8 11 10 12 14 8 11 7 10 8 7 7 5 4 4 9 7 6 14 13 6 14 7 8 8 5 5 5 12 1 7 11 10 5 3 9 5 7 7 11 7 7 5 10 6 6 5 5 7 3 9 4 7 2 1 6 5 8 6 7 10 5 6 5 5 6 5 6 6 7 5 5 2 4 9 7 7 7 3 8 7 3 4 0 4 1 3 2 2 1 4 6 1 4 3 5 5 4 3 7 3 8 3 4 1 5 7 4 3 5 3 6 5 5 6 4 3 2 7 3 7 5 7 2 4 5 5 6 4 3 6 2 4 8 8 7 4 7 11 10 7 7 4 3 5 8 6 8 6 10 5 8 7 9 8 12 12 2 7 5 7 5 4 9 4 9 6 4 5 4 5 5 10 4 11 5 5 7 3 5 4 6 9 6 6 3 4 6 7 8 9 4 6 8 4 6 5 4 7 3 3 6 7 6 5 6 4 4 1 6 10 8 6 10 4 9 8 7 4 5 5 4 1 3 1 2 3 10 4 4 7 5 1 5 1 4 7 6 4 10 3 3 2 5 3 4 7 3 6 6 5 4 4 6 7 10 7 8 6 8 5 3 6 5 5 6 6 4 5 1 0 6 3 3 3 6 5 5 4 4 5 7 5 8 9 4 4 
];
B = [
0 0 0
 127273 26592 100681
 60768 13236 47532
 208842 49732 159110
 135773 29764 106009
 81813 17679 64134
 206121 50520 155601
 167873 38722 129151
 95671 21543 74128
 284696 69541 215155
 299464 68405 231059
 54718 12228 42490
 858600 207585 651015
 115110 27997 87113
 36895 8862 28033
 193558 55721 137837
 63172 17818 45354
 19594 5108 14486
 215564 62485 153079
 17745 4546 13199
 18749 4996 13753
 4523 1307 3216
 92 16 76
 4233 1188 3045
 320635 96485 224150
 21218 5662 15556
 27592 7725 19867
 332827 102427 230400
 19536 5685 13851
 41247 12193 29054
 530173 155172 375001
 39252 11914 27338
 69021 20967 48054
 373964 120172 253792
 245731 78870 166861
 405575 130392 275183
 756469 244237 512232
 632092 200122 431970
 378389 120008 258381
 881149 291717 589432
 361527 114271 247256
 24894 7912 16982
 821392 274159 547233
 13504 4374 9130
 23476 7567 15909
 1114033 378644 735389
 24515 7972 16543
 287720 92011 195709
 1497601 531414 966187
 283924 91592 192332
 9 4 5
 10020296 3643505 6376791
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
16 63 0 1
10 4 0 0
25 9 0 0
37 6 0 1
35 12 0 0
35 15 20 1
69 19 33 4
188 23 41 10
715 28 53 22
2469 38 87 41
5443 52 103 55
11688 87 136 82
23813 102 189 124
50742 149 280 208
102469 221 376 300
203984 408 515 521
334553 855 838 824
392227 1701 1200 1151
328285 2782 1697 1681
200621 3960 2146 2142
90539 4735 2570 2681
23944 5121 2961 2984
6044 4408 3180 3156
4625 4055 3361 3224
4386 4088 3524 3413
4439 4286 3511 3638
4548 3786 3594 3615
4509 3911 3919 3871
4788 4230 4223 4221
4811 4392 4384 4556
5083 4639 4889 4917
5608 5086 5176 5060
6048 5630 5584 5579
6549 6191 6109 6314
7084 6847 6823 6794
7878 7665 7827 7624
8773 8509 8615 8491
9882 9652 9751 9692
11090 10808 11267 10990
12516 12246 12303 12424
14163 14114 14196 14017
16339 16368 16173 16050
18375 18469 18453 18510
20859 20966 20999 20932
23823 23992 23867 23707
27139 27418 26928 27506
30393 30809 30728 30241
33765 34150 33974 34016
37829 37910 38056 37952
41842 41707 41548 41440
45412 45666 45953 45713
48795 49160 49122 48718
52572 52120 52141 52203
55452 55226 55449 55313
59389 58679 59623 58733
62507 62416 62452 62385
66954 67321 67070 67043
71463 71734 70485 71496
76244 76291 76591 75564
80031 80138 80244 79765
83912 84835 84471 83598
85682 85321 85185 85239
81952 81780 81973 81627
71700 71427 71230 71318
52854 53040 53165 52078
28826 28939 29179 28749
12098 12520 12709 11819
6775 6640 7129 6378
5280 5292 5250 5057
4637 4763 5402 4353
3210 3308 3207 3499
2192 1961 1928 2226
172 162 138 139
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
