A = [
2262060 2556267 73801757 2330497 2369211 1891664 1745453 1715992 1511991 1548718 1619424 1468142 1653880 1553512 1563382 1711368 1478835 1638633 1674971 1510816 1542269 1516691 1436492 1464839 1427530 1347587 1449171 1404504 1352821 1369006 1399729 1435710 1380375 1386631 1416471 1412081 1400701 1375765 1375116 1523298 1429546 1425879 1538953 1498935 1494971 1494056 1439551 1497331 1448438 1367484 1381835 1253916 1258107 1234310 1149931 1090575 1111765 1155865 1063078 1024458 1068182 1030311 1012177 991010 967460 978467 945277 936189 934374 903878 898466 904327 884355 894007 905334 896240 895285 900175 873972 853490 845616 841406 816534 807329 813938 784808 757890 711933 689835 693512 680845 669683 673754 667050 658937 658333 654876 654176 643181 635085 639403 629376 623590 624724 619121 617092 615199 608750 608984 603343 601776 602610 598923 600764 598216 597407 599815 594957 588090 588446 593019 588134 584259 582518 578609 576919 577342 569756 567344 561080 556342 552947 550193 546202 548029 541342 535940 534474 532400 523157 522661 517540 515998 513262 506758 504722 501593 495112 489914 485480 481196 476663 472546 465771 461069 454848 455332 449546 444266 437094 434631 429798 422441 418920 416358 409469 407512 402634 400235 395697 390245 389823 390491 390056 395816 379364 373791 372288 362745 359588 354107 351606 351104 344412 343832 342300 336268 335162 333797 334356 331648 326532 326390 322908 319297 316910 315176 315441 310547 306537 305440 305986 302623 300631 299437 298150 296602 292603 287466 283494 277965 272299 272463 268344 270779 268808 266283 267400 266146 259554 258175 253118 249400 245949 236614 229392 223281 216329 209889 204408 198855 195189 193115 188650 187349 183210 180207 179492 176178 174631 172842 169965 166914 164629 162960 159898 157286 154753 153474 151750 149419 145829 144045 141693 139639 137875 136320 133648 131757 130496 128465 126162 124177 122949 120085 118542 116630 115686 113903 112017 111549 109591 107741 105924 104222 103607 102451 101050 98822 98019 96140 95483 94047 92509 91836 90501 89219 87630 86631 84863 84302 82469 81567 81193 79688 78231 77489 76621 74485 73377 72391 71667 70513 69463 68492 68268 66653 66033 64611 64259 63240 62774 61499 59943 59474 58942 57679 57010 56153 55663 54703 53719 52659 51792 51872 50909 49746 49230 48874 48146 47394 46568 46494 45465 43981 44285 43258 42502 42176 41794 41166 40436 39643 39137 39338 37878 37680 37320 36142 35965 35425 35282 34727 34001 33497 33246 32789 32231 31536 31455 30644 30214 30139 29758 28930 28934 28159 27897 27182 26573 27112 25937 26081 26867 25047 25082 24501 24276 23993 23483 23446 22442 22316 21302 21350 21543 20905 20780 20093 19855 19799 18995 18580 18828 18422 18634 17779 17689 17687 17342 17193 16584 16638 16120 16216 15929 15790 15300 15569 15098 14853 14273 14136 13909 13942 13624 13508 13325 13182 12935 12547 12260 12403 12026 11759 11852 11747 11366 11069 11092 10758 10601 10623 10547 10416 10413 9866 9964 9514 9664 9295 9351 9054 8785 9219 8513 8521 8409 8650 8038 8073 8092 7798 7795 7448 7427 7519 7471 7268 7146 7027 6807 6937 6620 6720 6424 6346 6157 6241 6045 6038 6096 5803 5920 5708 5562 5562 5318 5417 5293 5205 5044 4954 4976 4909 4873 4619 4699 4520 4474 4563 4362 4292 4223 4226 4230 4171 4096 4117 3896 3789 3907 3741 3668 3786 3620 3549 3503 3332 3320 3244 3287 3257 3170 3129 3035 3053 3038 2936 2903 2828 2843 2951 2749 2669 2713 2729 2578 2632 2494 2622 2514 2404 2391 2295 2353 2343 2177 2078 2195 2133 2078 2165 2093 1990 2145 1890 1937 1819 1801 1726 1808 1792 1723 1646 1648 1541 1656 1672 1608 1383 1560 1572 1464 1410 1439 1415 1500 1289 1391 1409 1286 1220 1271 1194 1230 1191 1189 1181 1192 1141 1135 1161 1043 1078 1041 1007 1033 980 1027 1010 1059 1020 971 934 846 947 868 860 800 835 783 854 790 772 717 761 742 828 805 749 680 691 745 723 701 655 708 680 641 598 709 655 630 604 656 560 538 522 581 592 583 531 513 500 485 557 581 526 499 494 496 506 454 474 480 496 400 480 471 462 424 410 436 402 412 365 393 440 375 315 399 410 362 378 335 332 322 302 333 303 326 284 316 300 308 293 315 299 326 312 285 302 251 280 300 309 263 275 279 335 227 259 255 228 243 246 215 197 192 281 260 214 224 226 176 213 231 225 185 222 176 180 191 225 177 189 161 210 153 184 251 176 173 185 178 154 140 187 183 185 162 198 173 171 167 163 164 190 160 208 150 170 187 148 138 140 182 172 144 142 137 145 125 129 144 168 96 131 126 135 133 133 133 114 129 130 131 104 124 102 101 106 179 105 129 88 92 99 93 86 114 97 90 124 112 81 111 80 89 76 87 65 85 80 87 99 63 93 95 77 74 106 77 84 82 99 95 81 81 97 86 83 58 79 64 53 87 61 78 55 96 67 84 82 56 54 76 106 69 76 70 66 51 91 69 52 59 72 67 55 64 47 66 57 60 76 58 44 79 67 63 56 57 65 73 56 56 63 52 57 51 60 68 49 56 48 67 60 48 42 40 40 51 46 46 40 35 46 51 36 65 33 34 47 47 48 57 34 46 32 40 42 39 49 47 47 26 44 41 28 32 47 42 33 32 37 32 38 53 36 44 60 48 47 37 36 37 62 46 35 37 45 36 39 30 38 49 72 39 46 46 38 49 34 41 37 24 28 34 28 48 39 35 42 30 28 36 29 45 50 26 37 26 27 39 23 41 25 33 23 31 35 31 33 27 41 34 33 31 26 32 46 50 25 36 49 27 30 24 31 24 31 19 32 40 23 20 44 36 41 41 28 35 31 33 31 34 28 25 14 32 33 25 29 30 29 38 26 30 33 22 29 27 20 28 31 23 22 37 30 24 18 20 20 12 20 25 35 19 23 23 22 31 33 25 23 26 16 21 19 20 31 35 24 19 24 34 26 32 17 26 29 28 43 37 67 65 61 54 102 68 79 82 117 82 72 63 84 86 82 75 77 86 74 74 71 67 96 80 81 84 69 95 86 89 92 101 87 86 107 96 88 78 90 80 82 79 83 81 88 98 90 119 105 229 107 136 191 134 151 119 125 124 141 1126 228 169 124 143 69 53 66 67 42 43 35 32 35 44 36 39 44 20 48 20 23 22 38 42 29 30 26 15 28 95 29 28 34 19 29 17 17 24 29 19 17 337 29 31 59 52 160 139 96 103 86 71 27 27 15 17 32 27 16 28 16 26 28 3 26 2 13 19 90 12 17 11 10 17 5 8 18 11 13 9 5 5 9 13 11 8 9 10 15 27 14 17 38 17 7 18 13 25 12 54 14 17 16 13 39 13 11 27 15 21 25 13 27 43 32 29 39 29 16 43 24 25 34 39 44 29 37 31 26 27 20 27 46 53 41 31 47 44 48 37 57 51 53 65 52 47 52 60 63 59 39 38 46 52 67 41 40 45 50 16 26 21 31 26 17 40 60 32 30 37 25 22 27 27 31 33 31 28 36 48 43 31 28 25 24 29 27 41 35 42 42 37 45 26 37 35 50 46 27 33 23 28 36 52 42 32 40 42 27 38 19 22 17 15 57 8 30 25 8 25 4 17 23 144 7 12 5 5 15 24 12 7 7 11 11 7 5 16 58 15 7 9 2 16 8 6 12 3 7 9 9 8 11 26 13 14 10 7 7 7 14 12 14 13 4 11 12 15 14 10 10 6 2 11 9 8 24 7 10 10 6 13 12 13 20 31 17 151 10 18 21 20 9 16 27 15 22 29 183 21 17 31 47 21 24 14 27 22 18 37 7 20 19 64 33 28 31 15 25 24 26 25 22 22 30 16 22 25 23 33 30 23 28 35 30 24 15 33 50 32 36 34 31 63 35 29 40 31 39 61 41 32 42 31 33 20 19 55 92 29 45 41 42 46 41 38 49 56 64 52 33 38 75 3 116 52 17 35 52 56 25 49 38 33 48 41 55 41 49 66 56 34 51 56 84 46 38 59 72 76 42 55 45 69 57 54 54 52 82 74 30 51 36 67 79 80 12 5 1 4 5 22 3 9 6 55 65 51 58 83 41 65 66 64 77 57 61 70 70 120 79 83 121 141 77 77 100 59 111 95 59 83 84 71 113 105 44 147 194 137 159 117 116 103 128 84 69 103 120 176 125 75 132 129 94 113 8 9 11 7 7 5 9 12 13 9 5 3 9 5 11 8 12 3 8 9 48 15 21 7 15 10 6 10 9 18 6 10 11 5 14 3 12 10 10 5 5 12 6 10 9 15 5 9 7 7 3 9 7 7 2 10 10 7 9 4 4 9 9 6 3 1 4 1 3 6 8 4 6 6 5 4 3 4 1 7 2 1 6 2 16 2 7 5 1 3 4 3 4 4 1 5 3 2 2 7 8 3 6 2 8 4 4 4 2 7 7 2 4 2 2 4 4 2 6 5 4 4 3 0 1 4 2 3 3 3 5 4 7 1 4 1 4 0 8 3 3 6 4 27 10 7 3 6 3 7 2 8 1 3 0 2 7 2 3 1 5 6 3 1 0 0 1 1 3 4 4 0 5 2 1 0 4 7 11 3 4 2 2 4 5 2 5 1 0 12 2 1 6 3 0 8 2 5 9 2 6 7 9 3 4 7 1 4 4 3 3 5 2 2 4 1 6 1 3 1 1 0 0 1 0 1 4 1 3 0 2 6 7 0 0 4 0 6 1 4 2 0 0 2 5 0 1 2 0 2 0 1 0 2 1 3 3 3 4 3 1 5 7 4 3 0 0 1 0 1 2 0 1 4 1 3 4 2 3 5 1 2 0 7 9 5 7 14 7 14 5 5 3 4 2 5 5 5 5 8 2 12 5 8 9 1 9 2 3 6 10 4 5 4 3 3 6 2 3 4 1 3 8 3 1 3 2 4 4 3 0 8 10 2 14 7 3 13 6 2 6 9 8 9 4 8 4 8 2 7 1 3 0 3 7 9 3 7 13 4 3 1 5 2 0 4 9 2 0 2 10 3 1 3 12 3 6 3 2 7 9 2 6 4 2 15 7 5 2 5 1 2 3 0 2 4 1 1 2 1 0 2 6 2 1 1 3 4 
];
B = [
0 0 0
 815974 475149 340825
 1616965 1169190 447775
 904084 583745 320339
 713462 450508 262954
 566731 342397 224334
 346188 206323 139865
 190890 106898 83992
 250939 161010 89929
 458015 285141 172874
 1149134 879279 269855
 768016 529134 238882
 723439 507053 216386
 701098 496514 204584
 681343 491161 190182
 958380 735868 222512
 753483 552942 200541
 739435 542342 197093
 711659 521680 189979
 691671 504358 187313
 901945 693475 208470
 744791 554121 190670
 745525 555165 190360
 735407 552449 182958
 706290 527750 178540
 860290 662098 198192
 734441 554154 180287
 732838 552893 179945
 735342 556992 178350
 722151 546100 176051
 830474 639384 191090
 746103 569483 176620
 732886 559707 173179
 738435 564724 173711
 721407 551240 170167
 803478 621584 181894
 735620 565621 169999
 760691 576849 183842
 723789 556313 167476
 728339 560093 168246
 791674 607345 184329
 723038 558235 164803
 739130 566873 172257
 707430 548274 159156
 689901 533977 155924
 766994 593893 173101
 695247 539988 155259
 721412 559349 162063
 698723 546613 152110
 690429 534636 155793
 706048 553325 152723
 691659 539773 151886
 675950 529864 146086
 672236 524770 147466
 657163 517660 139503
 686755 540351 146404
 653609 512178 141431
 643271 507943 135328
 648548 511402 137146
 638497 507151 131346
 109348833 102148453 7200380
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
29 14 0 0
11 0 0 0
9 20 0 2
15 8 0 1
33 12 0 0
16 25 0 2
46 62 0 1
164 47 0 0
59806 110 0 0
742451 108 0 0
2298819 98 0 1
5760510 256 2 1
11388846 159 7 3
19712288 228 43 32
28143309 271 83 52
27050102 342 100 96
17192138 328 231 235
10680194 547 386 363
5740204 560 603 562
2502706 1021 765 726
763575 922 953 911
127063 966 1080 1083
8443 1226 1345 1290
2225 1345 1435 1463
2386 1666 1748 1764
3296 1982 1961 1978
2855 2115 2235 2193
3193 3898 2664 2443
3554 3661 2825 2757
3625 3312 2983 3045
4082 3713 3267 3334
5667 13216 3395 3355
4063 4490 3534 3786
4662 3926 3820 3740
20128 5259 3686 3601
8492 4315 4629 3834
4075 7040 3795 3809
4147 4004 4041 4332
4307 4655 3850 3920
4411 4276 4137 4347
4479 4423 4959 4160
4532 4593 4321 4361
4823 5374 5331 4936
4838 4717 4957 4671
5148 5563 5384 5216
6361 5561 5360 5189
5384 5326 5536 5483
5474 5320 5660 5714
5822 5810 6440 5759
6093 5858 6236 6266
6296 6401 6742 6292
6125 6061 6757 6495
6543 6450 6488 6720
6139 6212 6471 6509
6138 6282 6340 6318
6199 6344 6223 6230
5886 6121 6381 6407
6347 6117 6418 6027
6011 5781 6455 6147
5937 5966 6380 6169
6292 6000 5974 5867
6146 6425 6291 6300
6411 6855 7150 7120
6905 7055 7224 6960
7397 7608 7509 7628
8235 8249 8589 8314
9332 9184 9308 9318
20465 27267 13345 12852
11338 11366 11770 11472
13219 13058 13117 14332
14286 14144 14199 14449
15997 15931 17201 16880
17575 17461 17804 17625
18613 18845 18718 18602
19319 19246 19281 18992
20473 20811 20142 19969
18833 19375 19067 19352
16144 16003 15831 16101
15599 15673 15658 15741
14969 14787 14735 14915
8367 8434 8641 8732
5437 5183 5396 5270
333 336 325 317
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
