A = [
406160 429027 1628379 419634 440422 397704 388028 398639 386558 358418 357956 363234 359525 354062 350783 345819 341468 339610 335322 332906 331831 326401 325806 324167 322485 366771 365300 364126 408620 408860 409885 411284 413103 413700 412544 411019 405880 401922 399407 394969 391993 390933 388040 386255 386392 381004 378648 374123 370272 367349 363946 361159 360071 358630 355629 352992 350209 345927 343769 339579 335986 333673 332816 331349 326128 325603 322923 319375 316903 312475 310123 307077 304232 301110 300258 297929 295410 292224 288538 286284 283722 280647 278508 276642 273350 271152 268444 266201 264545 261912 258307 256471 254149 251321 249250 245741 245166 241816 241157 237430 235186 234211 230299 229273 227302 224308 222081 221951 218394 217155 214825 211561 210386 207933 206299 204052 201389 199840 198446 195889 193652 192070 189398 188020 184901 184228 182140 180454 178339 177033 174779 172826 169863 169075 168106 165483 163650 162321 160442 158742 157027 155661 154170 152173 151217 149441 147487 145740 144407 142200 141732 139482 138219 136658 134605 133990 132350 130765 129877 127314 126484 124786 123120 121376 119311 118680 117573 116183 114486 113020 111987 111948 109075 108451 106629 105016 104529 103035 101851 100478 99623 98749 97197 96007 94769 93613 92513 91359 90848 88856 88492 87029 85815 85069 83890 82847 81894 81677 80752 78943 77867 76939 75944 74601 74251 73079 72479 71001 70724 69381 68852 68372 67028 65688 65255 64629 63860 62844 62609 61584 60603 60214 58961 58016 57674 56115 55614 55352 54480 53591 53063 52502 51394 50929 50005 49638 48766 48326 47321 46998 46283 45743 45179 44513 44197 43205 43250 42422 41921 41569 40740 40386 39850 39193 38325 38212 37715 37083 36481 36027 35945 34779 34637 34341 34019 33145 33110 32183 31961 31827 31245 30760 30781 29943 29721 29207 28814 28410 27975 28046 27178 27165 26993 26206 26302 25557 25292 25437 24951 24344 24348 23757 23403 23642 23120 22894 22613 21835 21790 21808 21167 20731 20680 20652 20180 19980 19710 19475 19467 18812 18814 18497 18154 18006 17910 17558 17312 17202 16704 16250 16436 16115 15593 15506 15090 15190 14974 14612 14425 14102 14238 13830 13676 13853 13473 13309 13064 13206 13067 12544 12771 12551 12316 12304 12057 11865 11781 11581 11377 11062 11000 11470 11020 10605 10410 10330 10987 10106 10372 10034 9942 9962 9557 9730 9297 9426 9194 9112 8887 8744 8818 8512 8460 8510 8327 8274 8264 7973 7937 7730 7808 7576 7569 7539 7722 7296 7114 7398 7103 6916 7072 6935 7059 6871 6680 6723 6500 6372 6210 6333 6238 6031 6045 6056 5866 5826 5691 5650 5613 5559 5470 5495 5259 5286 5280 5267 5132 5176 4978 4928 4747 4753 4736 4766 4592 4589 4503 4441 4611 4650 4379 4388 4422 4247 4302 4169 4241 4152 4109 3887 3984 3821 3798 3747 3780 3666 3605 3514 3615 3587 3584 3539 3453 3514 3487 3310 3403 3287 3290 3242 3137 3107 3077 3072 3233 3124 3031 2970 2954 3083 3036 2833 2764 2903 2793 2696 2760 2724 2610 2538 2603 2612 2529 2561 2544 2578 2593 2465 2461 2482 2415 2474 2352 2345 2344 2427 2332 2337 2247 2187 2269 2233 2184 2253 2167 2206 2182 2094 2227 2122 2040 2040 2047 2038 2026 1989 1974 1979 1897 1967 1914 1882 1925 1817 1925 1805 1782 1786 1824 1830 1847 1829 1752 1769 1781 1782 1705 1726 1746 1811 1813 1655 1702 1777 1707 1829 1764 1881 1844 1619 1749 1663 1655 1652 1685 1652 1542 1574 1549 1540 1538 1641 1520 1637 1618 1440 1331 1414 1471 1305 1367 1507 1463 1513 1560 1490 1524 1486 1437 1378 1375 1362 1341 1413 1344 1271 1229 1321 1232 1260 1201 1247 1275 1301 1312 1206 1287 1225 1273 1275 1136 1130 1165 1165 1171 1107 1086 1135 1062 1069 1152 1100 1092 1045 1069 999 1100 1029 1069 1053 990 1012 1025 982 972 925 918 971 970 983 916 967 920 969 902 893 936 923 850 946 929 877 843 868 846 846 868 852 818 837 795 860 823 860 793 846 772 776 759 851 811 777 814 763 809 776 813 750 711 737 738 802 734 722 734 742 740 740 739 712 702 715 720 693 672 698 654 674 683 693 730 725 680 703 652 694 700 652 630 673 660 639 600 611 650 637 658 632 622 594 606 595 565 634 614 567 594 544 625 642 610 626 685 633 589 623 563 609 574 597 614 648 661 660 718 909 767 666 724 702 642 614 652 713 621 600 686 645 619 639 627 694 628 602 589 583 562 587 521 531 503 496 479 534 480 499 502 566 505 553 565 568 517 631 539 525 475 555 497 468 480 517 511 483 535 484 501 556 434 477 474 461 428 497 444 472 472 458 475 465 470 416 432 454 489 445 422 429 481 401 367 394 432 400 395 416 359 420 378 382 385 396 406 367 358 392 397 350 348 375 377 394 411 396 399 414 388 399 386 345 436 405 407 380 381 346 351 349 338 377 355 358 375 336 358 357 328 300 328 339 341 306 276 285 297 314 327 289 304 292 277 336 354 349 335 306 338 358 306 359 293 320 304 312 317 296 281 310 322 271 306 282 292 297 294 272 311 286 286 293 267 245 257 239 277 282 275 285 261 280 263 245 253 232 265 253 239 264 280 283 373 279 264 257 292 266 253 258 233 240 243 255 209 224 230 197 218 209 249 235 236 242 204 222 199 203 245 258 212 211 185 218 227 211 219 237 214 238 201 228 214 197 193 183 177 201 229 170 185 188 177 200 185 164 191 165 177 177 157 150 192 219 188 169 187 169 192 175 160 186 184 163 133 180 182 168 172 159 181 197 170 167 180 150 167 160 169 181 166 181 164 163 151 156 166 154 187 153 174 170 137 149 166 147 169 158 153 151 153 143 172 161 184 155 170 153 161 168 157 152 174 141 154 141 137 171 167 156 160 164 155 171 152 138 162 163 165 156 162 163 145 160 179 165 154 170 154 151 161 148 169 135 172 149 131 146 130 132 130 143 146 151 147 126 138 158 123 147 137 154 119 126 137 117 126 143 143 123 105 130 118 152 135 128 102 130 134 125 132 106 138 113 114 126 129 131 140 122 118 150 117 130 100 128 123 132 122 126 126 127 114 116 123 120 109 121 113 125 108 129 101 98 135 130 97 107 109 103 133 119 112 103 116 107 107 123 102 121 127 125 114 110 105 101 118 105 117 112 114 142 126 125 119 122 117 93 125 104 125 109 113 113 143 100 130 102 131 131 131 121 94 111 85 107 81 114 117 95 111 95 87 113 93 78 92 96 80 78 84 77 85 86 95 74 84 99 92 108 102 87 86 85 81 82 63 97 89 86 88 79 80 96 90 75 82 67 82 59 71 75 81 68 73 74 80 56 90 78 79 68 79 75 62 76 80 75 69 71 78 95 69 78 88 95 87 85 62 72 64 74 73 93 68 66 70 61 69 62 54 78 61 72 68 72 80 77 65 82 57 72 67 81 85 92 71 92 65 80 62 78 64 69 59 58 71 62 59 91 67 73 63 57 65 65 69 55 66 44 62 61 63 83 62 55 53 53 45 50 58 54 56 60 56 52 46 59 46 61 43 55 67 63 51 44 52 45 49 54 68 53 57 55 57 48 47 65 57 59 43 53 59 46 62 53 46 71 58 54 58 53 45 53 59 43 42 38 46 42 52 37 52 45 51 62 62 49 46 51 51 48 57 46 56 58 48 48 58 51 56 39 44 52 51 44 59 51 53 47 64 58 51 51 64 66 60 64 68 58 65 59 59 68 48 61 60 60 69 39 47 54 62 64 50 48 61 56 42 63 49 42 42 47 53 46 48 45 54 47 49 27 37 45 38 59 34 42 55 38 41 50 41 36 34 44 39 51 47 25 39 43 37 34 38 26 30 40 34 43 29 37 40 37 25 33 29 38 32 40 38 25 25 33 36 28 35 41 37 35 37 28 33 35 37 39 43 42 32 47 40 38 36 32 43 28 34 38 39 42 39 33 42 38 33 31 32 42 28 29 29 31 31 40 40 23 37 29 30 35 39 36 25 21 40 21 32 28 36 39 29 21 26 31 34 29 27 25 27 26 37 23 20 30 36 32 35 27 29 35 37 25 22 29 20 27 24 30 21 36 25 23 29 20 30 35 25 27 22 23 24 36 30 25 42 38 33 36 28 29 31 47 29 39 35 35 24 40 40 29 30 39 30 25 31 34 27 31 44 25 29 26 33 35 27 33 25 22 21 33 30 26 32 35 36 41 25 29 34 39 34 32 27 41 30 36 28 24 19 26 23 22 24 23 18 18 28 28 26 34 32 30 38 32 28 20 21 29 29 25 35 29 32 33 37 41 50 26 37 69 138 138 157 119 97 97 103 33 25 26 21 26 24 40 24 28 33 15 22 32 30 26 16 28 32 31 26 29 30 19 25 18 22 35 31 40 56 34 37 49 29 47 33 27 26 24 22 26 16 19 19 26 15 15 17 16 26 21 21 25 22 31 26 15 18 29 32 28 12 15 22 28 19 23 24 24 32 21 27 19 21 30 26 30 16 22 21 24 20 21 17 20 26 28 26 38 29 24 22 23 21 18 32 29 21 19 24 11 20 18 12 17 14 27 18 20 25 15 17 13 19 13 16 15 12 16 22 13 16 29 22 20 23 11 12 16 21 18 20 18 26 27 17 19 22 27 21 23 29 18 21 23 13 16 19 22 20 25 19 23 14 21 25 23 21 18 24 17 14 17 13 32 17 20 26 29 19 18 29 24 10 23 22 23 29 34 23 23 19 22 24 28 32 12 18 22 20 16 23 19 22 27 26 18 26 22 18 23 15 17 20 21 16 22 6 16 19 12 32 17 19 18 22 28 23 28 15 23 18 18 16 17 12 22 14 13 17 24 15 22 14 28 18 15 21 13 27 18 21 14 19 18 17 17 16 16 9 22 14 16 16 12 21 20 13 17 17 22 23 17 18 12 17 24 17 18 12 18 16 27 20 18 17 20 21 13 22 19 9 21 19 22 21 22 23 18 26 22 12 19 17 22 25 28 27 18 14 16 21 16 19 14 15 16 22 17 14 25 20 19 17 13 
];
B = [
0 0 0
 148417 50937 97480
 70882 24166 46716
 247947 98270 149677
 154653 55625 99028
 90239 31474 58765
 242517 99405 143112
 190139 71350 118789
 103865 38015 65850
 323270 131170 192100
 334431 127707 206724
 60457 21466 38991
 955549 393385 562164
 127686 50373 77313
 40888 15381 25507
 229827 108040 121787
 73148 32204 40944
 22194 8825 13369
 253824 121037 132787
 20347 7951 12396
 21301 8728 12573
 5016 1993 3023
 142 51 91
 5066 2256 2810
 378236 183732 194504
 24151 9734 14417
 32238 14152 18086
 398238 196846 201392
 22971 10565 12406
 49010 22638 26372
 611258 291216 320042
 45505 20584 24921
 80903 38069 42834
 453470 232806 220664
 305180 155495 149685
 510783 264604 246179
 937443 486775 450668
 742012 359120 382892
 471191 240207 230984
 1099692 579625 520067
 411159 192749 218410
 28852 13425 15427
 989581 514130 475451
 15366 7231 8135
 27222 12855 14367
 1366830 733905 632925
 28648 13726 14922
 331686 155533 176153
 1926869 1110537 816332
 334259 160974 173285
 12 7 5
 13500736 8074501 5426235
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
48 60 1 1
50 12 0 0
167 16 1 0
230 21 2 0
187 31 0 0
165 35 18 1
316 68 59 11
1379 92 72 26
7681 94 99 43
30537 148 182 75
69145 180 211 108
145749 262 299 161
288670 295 427 275
594988 397 575 398
1097116 566 774 637
1786479 708 1097 981
2132675 1006 1496 1388
1852720 1484 1962 1975
1257290 2094 2485 2473
664036 2859 2932 3010
257291 3488 3320 3406
61204 4093 3485 3478
13144 4345 3622 3561
8840 4100 3803 3756
7591 4527 3768 4117
6884 5176 3841 4122
7091 4575 4034 4075
6302 4575 4108 4244
6132 4945 4586 4531
5833 5017 4763 4576
5970 5330 5105 5084
6653 5726 5383 5441
7441 6689 5770 5799
8248 7164 6377 6440
8361 7606 7023 7094
8795 8149 7976 7652
9992 9034 8653 8865
10835 10194 9930 9844
11678 11318 11110 10991
12664 12384 12312 12443
14225 14059 14083 13861
15918 15899 16013 15810
17868 18043 17618 17807
20360 20263 20432 20239
22923 23312 22943 23038
26012 26512 26279 26925
29596 29693 29982 29433
33234 32959 32746 32943
36631 36706 36669 36994
40853 40232 40701 40215
44127 44179 44461 44279
46893 47054 46931 47212
49926 49833 49683 49256
52466 52371 51988 52016
55292 55230 55741 55093
56953 57329 56822 56834
60107 59873 60358 59870
63905 63314 63056 63301
66048 65115 65498 65442
68144 67734 68127 68366
71306 71446 70898 70324
71294 70842 71393 71169
69153 68012 68971 68253
59007 60068 59867 59790
43992 44756 44737 43626
25152 25747 25053 24891
11389 12166 11829 11495
7638 7483 7654 6920
6892 5948 6010 5742
5202 5576 6620 4868
4009 4169 4049 4248
3514 2703 3115 3198
261 280 196 190
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
