A = [
269736 271597 5466637 277471 287816 282252 285317 319548 320000 341483 368007 374773 402925 415315 430935 449384 457199 473410 486518 487777 489481 493528 493116 495419 498215 517264 520801 522419 538456 536768 537135 538360 536157 537616 538096 534832 534042 531099 532275 525650 524329 525978 522221 522692 522588 517372 514364 517517 515336 509856 510390 503056 500570 500717 493173 489319 489685 492009 482387 478974 479935 475302 471247 467778 464155 463583 458303 453637 449640 447528 444445 441467 437630 436005 432367 429503 425682 422974 416855 412064 408997 407072 401507 396425 393930 388428 381456 374695 368661 364646 359809 356718 352672 349316 343899 340514 336413 334796 330284 326431 322911 319096 315135 312134 307583 305082 300693 296159 294820 292071 288521 285426 280153 277878 275176 272650 269380 266071 262395 258900 255247 252200 249522 246812 242091 238740 235674 233383 229551 226685 224224 221160 218565 214875 211696 209362 206602 204339 201655 199043 195902 193659 191791 188688 185141 183354 181127 178347 176614 173410 171053 168240 166418 163873 161704 159137 156294 154521 152336 149737 147614 146336 143163 141629 138782 137480 134991 132737 130824 129551 126442 124880 122982 121663 120267 118761 116624 114456 112854 110948 109682 108434 106484 105535 103857 102349 101355 99334 97661 96519 95082 93412 91840 90205 88957 88216 86604 85369 83800 83083 81415 80315 78839 78017 77338 76022 74725 73936 72434 70783 69987 68478 67276 66162 65033 63994 63118 62054 61825 60737 59434 58706 57743 56562 55415 54475 53027 52348 51082 49638 48574 48222 47193 46256 45915 44552 43921 43460 42487 42358 41149 40958 40028 38987 38612 38063 37494 36570 35974 35354 34796 34074 33685 32962 32595 31813 31295 30835 30344 29417 29157 28449 27713 27180 26920 26188 25911 25393 25399 24316 24096 23630 23050 22417 22284 21560 21615 20903 20686 20432 20113 19338 19040 18557 18302 18211 17685 17386 16980 16705 16581 16064 16175 15253 15219 14773 14611 14394 14182 13551 13465 13174 13185 12626 12566 12264 11847 11738 11457 11306 10900 10983 10745 10390 10213 10034 9920 9546 9592 9257 9002 9025 8941 8829 8438 8238 8081 8020 7880 7522 7578 7408 7296 7084 6906 6845 6747 6481 6289 6198 6028 6012 5843 5703 5607 5550 5562 5336 5275 5189 5129 4860 4750 4855 4554 4539 4584 4462 4351 4250 4048 4075 4035 3884 3851 3804 3735 3528 3585 3475 3416 3437 3316 3228 3162 3039 2997 3011 2910 2884 2812 2725 2691 2572 2658 2535 2466 2367 2262 2272 2310 2264 2178 2138 2120 2021 1961 1999 1912 1946 1932 1861 1761 1767 1772 1715 1662 1629 1641 1558 1571 1576 1428 1461 1476 1428 1319 1364 1331 1291 1320 1247 1259 1238 1174 1127 1164 1127 1092 1099 1050 1048 1014 1021 979 978 954 995 913 882 849 885 826 834 818 777 783 756 740 797 730 737 731 668 685 674 682 646 638 658 606 577 604 579 576 579 563 562 544 543 533 488 518 433 485 510 520 468 478 433 441 437 440 412 395 434 383 389 382 432 361 378 377 379 367 334 329 329 362 335 336 344 303 325 334 338 322 295 286 248 286 268 257 317 257 250 256 265 246 262 258 263 229 277 244 248 207 239 233 222 219 214 212 193 215 202 194 204 187 183 199 187 189 178 209 202 192 173 168 156 177 170 162 164 153 167 170 139 175 143 166 140 158 129 146 152 140 129 145 151 146 158 124 126 140 135 142 138 119 132 135 134 109 129 104 131 113 115 119 124 113 103 120 124 107 101 119 102 130 90 109 102 87 97 105 85 105 98 96 97 95 96 98 104 91 93 83 74 102 88 81 88 75 82 92 72 100 81 96 88 89 78 90 70 76 61 89 69 70 79 86 85 56 82 83 66 77 73 73 79 75 64 69 80 76 65 70 63 57 52 66 56 67 59 59 57 72 50 68 54 56 55 61 60 64 61 61 56 48 58 55 75 50 49 54 37 55 55 43 54 49 41 48 50 53 60 50 62 50 43 46 45 51 42 44 37 42 59 40 45 52 48 40 41 51 52 50 39 41 42 37 43 51 42 31 41 48 35 38 39 40 45 42 33 25 38 50 40 29 35 39 35 34 39 31 28 34 44 37 43 30 32 30 37 34 30 43 41 35 32 24 30 27 31 29 17 33 46 36 27 36 26 20 29 29 30 40 30 30 23 32 24 36 24 18 23 31 30 35 32 26 26 27 27 29 25 26 26 28 27 20 22 30 17 32 21 29 23 29 21 20 24 20 25 20 32 25 22 23 27 21 25 25 27 21 25 15 20 19 22 17 19 21 19 29 25 15 25 15 21 23 21 15 13 17 21 17 25 19 16 14 21 19 26 19 23 21 16 24 17 15 13 17 9 18 15 22 15 13 12 10 17 12 9 20 22 23 19 27 16 15 22 17 19 20 6 19 11 14 22 14 12 19 11 13 22 14 14 16 12 18 24 14 10 17 18 17 14 13 15 13 22 12 22 16 21 14 15 23 17 11 16 15 19 11 11 13 11 16 16 13 13 14 18 19 15 18 17 20 21 11 15 21 14 13 17 13 16 18 8 12 17 14 17 13 15 14 15 10 16 14 19 15 15 7 10 15 10 11 7 10 10 13 9 7 14 14 11 9 10 15 6 8 8 8 13 9 8 12 6 11 5 9 12 8 9 6 14 11 12 9 12 11 5 9 11 11 10 10 9 18 7 8 6 5 10 7 10 6 7 5 9 6 8 6 5 11 10 5 6 10 5 5 10 14 7 5 3 9 9 7 9 10 7 9 6 8 4 14 15 10 11 11 10 4 9 10 9 7 11 8 9 9 13 20 9 6 7 4 6 8 12 12 5 9 8 9 3 5 13 4 2 3 10 2 7 7 8 6 6 6 4 5 4 10 4 7 13 9 6 10 8 5 6 7 4 4 3 7 6 5 8 6 9 2 7 5 6 4 8 3 2 6 5 4 5 6 5 4 1 4 4 5 4 9 4 3 3 4 3 5 2 5 3 6 8 6 4 4 6 7 6 8 6 3 9 10 10 3 10 6 7 43 37 37 37 40 34 41 29 47 29 39 46 40 20 29 17 9 2 5 5 10 7 2 4 2 4 4 5 6 5 7 4 3 4 2 3 7 4 4 2 5 2 5 3 2 10 6 14 14 5 11 3 8 6 7 5 2 1 8 4 8 0 5 1 5 6 4 5 2 2 4 2 8 4 5 2 4 4 3 6 4 3 4 3 6 5 2 3 3 3 1 5 5 3 3 2 6 2 8 2 2 1 1 2 0 5 3 2 5 3 3 2 6 6 3 4 27 15 3 3 1 4 3 3 5 2 1 5 2 6 7 5 4 3 2 2 8 3 2 2 5 1 2 7 5 2 1 2 2 2 4 0 0 5 0 1 2 2 2 3 1 3 3 2 4 1 2 4 3 1 3 2 2 2 5 0 2 1 1 4 1 1 4 2 4 4 4 3 0 0 2 3 4 2 4 1 2 0 4 3 4 4 3 2 2 3 1 3 4 5 2 2 3 5 0 2 4 5 5 3 1 3 1 2 2 4 1 3 2 2 2 1 3 2 4 3 2 2 2 2 3 3 0 0 1 1 1 0 3 0 0 2 1 0 3 3 0 6 0 3 1 1 1 2 1 2 4 2 2 1 0 3 1 2 2 2 0 2 1 0 3 0 0 0 8 1 2 1 2 1 2 0 2 2 0 2 2 3 2 1 1 3 2 0 3 2 1 2 1 2 1 2 2 1 0 1 1 1 3 1 1 2 1 7 2 3 3 6 10 8 6 7 1 3 5 3 3 4 1 4 1 7 5 2 1 2 2 1 0 6 0 1 2 2 2 0 2 1 2 1 2 2 2 0 4 3 5 1 4 1 4 2 3 3 1 1 1 4 3 6 4 2 3 3 3 3 3 1 3 5 2 1 3 4 2 2 2 3 2 1 2 1 0 1 0 2 1 1 3 2 2 3 0 1 1 2 0 1 5 3 1 0 1 1 2 1 4 1 2 1 0 1 2 0 1 0 1 0 2 1 2 4 3 3 0 1 2 0 1 1 1 1 1 2 1 1 2 0 2 1 0 0 2 0 3 2 1 1 1 3 0 2 0 3 1 2 2 1 3 2 2 3 1 2 0 0 2 1 1 3 1 1 4 0 1 1 0 1 3 1 1 1 1 1 0 3 0 2 1 3 4 4 6 1 4 1 1 0 2 1 0 0 0 1 3 1 1 4 2 1 0 0 3 1 2 0 3 2 0 2 2 2 1 2 1 1 1 1 2 2 0 2 2 2 1 0 2 1 2 0 0 1 0 1 0 2 0 0 1 2 0 3 0 1 3 1 1 1 1 1 1 1 1 1 1 1 0 1 2 3 1 0 0 3 1 1 0 1 0 2 1 1 1 2 1 1 0 2 2 0 0 1 2 2 2 1 3 2 0 1 2 0 0 1 1 2 0 0 0 0 3 0 0 2 1 1 1 0 0 2 0 0 0 0 1 1 0 2 1 0 1 1 2 1 0 0 1 3 0 2 2 1 0 0 0 0 1 1 0 2 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 2 0 0 0 0 2 0 1 0 0 0 0 0 0 0 1 0 1 0 2 1 0 0 0 1 0 1 2 0 0 3 1 0 0 0 0 0 0 0 1 4 3 3 1 6 1 0 1 2 1 1 3 3 1 0 0 1 2 0 0 0 2 0 1 0 0 2 3 0 1 0 1 1 0 0 3 4 0 0 3 0 1 2 4 2 1 4 5 3 1 1 2 0 0 0 0 2 3 1 3 0 0 4 0 0 0 0 0 0 0 0 3 1 2 0 0 1 0 0 0 1 1 1 1 1 3 1 0 0 1 0 0 0 0 1 3 2 1 1 0 2 0 0 1 2 0 0 1 0 0 1 1 1 
];
B = [
0 0 0
 532498 332843 199655
 249688 152764 96924
 560326 382305 178021
 488947 325945 163002
 247310 164677 82633
 646863 464832 182031
 262758 181673 81085
 517698 383714 133984
 528023 392645 135378
 121312 86718 34594
 860476 697384 163092
 239459 183043 56416
 82478 62561 19917
 432771 348705 84066
 158175 122740 35435
 41872 32855 9017
 467241 382719 84522
 32029 25057 6972
 29762 24189 5573
 6859 5393 1466
 6116 5101 1015
 11639 9575 2064
 735338 599697 135641
 47656 37924 9732
 59372 49130 10242
 696290 580434 115856
 57877 48401 9476
 57871 49942 7929
 977888 834418 143470
 73359 64613 8746
 76998 69460 7538
 682279 599687 82592
 117439 109744 7695
 752638 675614 77024
 211426 201494 9932
 169047 161181 7866
 1179667 1098261 81406
 402384 389370 13014
 647018 628375 18643
 1377599 1302849 74750
 699602 679830 19772
 535540 518789 16751
 1320303 1259088 61215
 479082 467566 11516
 277273 268089 9184
 1399755 1345454 54301
 272057 263506 8551
 53744 51842 1902
 2858722 2781971 76751
 64291 62233 2058
 207771 201675 6096
 5025104 4925680 99424
 219719 214614 5105
 3 3 0
 9507502 9366090 141412
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
9 14 0 0
1 1 0 0
3 10 0 0
12 11 0 0
13 4 0 0
22 10 26 0
1592 19 63 8
12173 12 92 23
55655 13 122 24
197673 30 146 33
490663 35 196 54
1161463 32 260 105
2346111 43 313 140
4242241 65 388 215
5886964 123 476 327
6674173 190 659 490
5656660 282 840 765
3551716 380 1126 1119
1573125 587 1537 1575
408457 841 2013 2150
50117 1256 2557 2529
5399 1635 3031 2995
4027 2364 3519 3547
4458 3090 4072 4121
5145 4161 4776 4968
5773 4913 5570 5536
6574 6100 6314 6511
7451 6792 7153 7183
8128 7716 7825 7828
8736 8478 8435 8682
9472 9087 9126 9105
9729 9510 9541 9367
9794 9937 10041 9826
10110 10135 10184 10105
10304 10221 10170 10202
10472 10619 10392 10512
10779 11040 10658 10790
10819 10691 10743 10669
11202 10802 10917 10930
11121 11091 11065 11039
11444 11456 11394 11104
11881 11742 11830 11836
11990 12282 12007 12078
12623 12839 12583 12544
13224 13303 13149 13205
13778 14067 13823 13736
14333 14566 14483 14288
15176 14988 15074 15372
15282 15647 15481 15756
16231 16477 15975 16005
16556 16510 16470 16551
16500 16675 16705 16810
16582 16679 16746 16854
16099 16357 16401 16607
16031 15970 15876 15839
15441 15149 15498 15537
14497 14597 14456 14688
13746 13608 13745 13485
12546 12550 12308 12469
11333 11559 11330 11649
10419 10330 10407 10418
9496 9713 9434 9492
8692 8846 8768 8714
8319 8283 7954 8102
7953 7748 7792 7768
7677 7621 7719 7689
7675 7751 7757 7758
8233 8123 8091 7879
7759 7808 7878 7754
8145 8028 7973 8168
8088 7964 8182 8237
7933 7893 7994 8210
7798 7892 7767 7910
7225 7193 7275 7154
6491 6619 6555 6589
6177 6144 5886 6055
4994 5132 5081 5013
3730 3734 3839 3691
3368 3265 3341 3285
2832 2861 2865 2910
1678 1678 1618 1597
928 924 980 963
49 68 58 59
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
