A = [
459077 491461 1898013 341194 377689 326505 316371 321627 312076 291990 290948 291413 290892 283137 282226 275869 271507 271249 267331 265388 264124 261505 259397 259206 260197 315575 317141 319218 374425 377218 381419 383566 386201 389738 390582 389290 384892 382553 380348 377129 374976 374259 370859 370135 369990 366818 363956 360794 357185 353054 352227 349270 347951 346404 344717 341784 339581 336586 333043 330430 326861 324042 321888 319261 317934 317052 313353 311874 309266 305365 302942 299881 296864 293994 292778 289168 288213 284990 282870 279735 277136 273923 271695 269771 266695 264459 261916 259540 256965 254400 251400 249212 247601 243735 242861 239658 237499 235528 233371 230638 228989 226334 223183 220263 219803 217060 215989 214198 210733 208752 205947 203846 201935 200341 198107 195083 193466 191645 189452 186950 184698 183470 180951 178343 175756 175505 172951 170769 168905 166478 165356 163299 161286 160676 158021 155369 154214 152338 151076 148642 147165 145398 143577 142703 140625 139208 137177 136129 134640 132730 132435 129668 128095 127000 124993 123431 121726 119937 118973 117434 115905 114631 112319 110637 109068 107930 107049 105787 104267 102676 101738 100391 98710 97738 96010 94896 93977 92386 90907 90586 89152 88194 86824 85378 84992 84161 82618 81179 79969 79186 78596 77223 76258 75040 73797 73780 72095 71547 70444 69063 68635 67305 66386 65100 64728 63684 62948 62341 61821 60924 60041 59095 58547 57704 56552 56203 55430 54805 53337 53270 52551 51939 51113 50434 49722 48911 48092 47837 47067 46081 45502 45363 44186 44125 43284 42385 41883 41372 40733 40351 39685 39228 38860 38408 38252 37228 36956 36260 35818 35157 35068 34545 34447 33779 33369 32655 32288 32170 31308 30980 30938 30010 29687 29459 28796 28300 28398 27792 27439 26941 26878 26568 25949 25915 25444 25307 24845 24130 24308 24091 23653 23102 22981 22986 22734 22216 21680 21695 21498 20955 20896 20456 20157 20347 19909 19738 19254 19061 18964 18387 18448 18325 18154 17945 17884 17217 17223 16978 16809 16602 16362 16293 16111 15607 15595 15169 15364 15146 14596 14427 14503 13783 13551 13680 13335 13155 12936 12731 12641 12490 12305 12196 12289 11777 11749 11581 11640 11310 11050 10973 11209 11039 10808 10678 10520 10382 10207 10244 9913 9796 9940 10639 9557 9670 9455 9201 10316 9047 9073 9009 8886 8722 8610 8695 8285 8482 8262 8052 7844 7889 7904 7583 7615 7552 7354 7356 7337 7097 7245 6951 6997 6852 6711 6583 7143 6634 6388 6428 6351 6362 6457 6304 6559 6364 6059 6009 5776 5629 5649 5622 5672 5579 5225 5325 5361 5270 5107 5132 5241 5021 4903 4869 4943 4814 4965 4815 4709 4589 4466 4435 4449 4488 4265 4253 4235 4277 4128 4074 4194 4028 3959 3982 3972 3954 3913 3935 3964 3828 3700 3587 3590 3509 3523 3464 3409 3410 3357 3363 3297 3300 3300 3283 3265 3109 3189 3076 3113 3070 2974 3002 3048 2956 2900 2898 2921 2885 2818 2985 2855 2740 2990 2806 2726 2729 2679 2640 2529 2577 2580 2621 2437 2447 2469 2339 2432 2365 2387 2371 2330 2448 2346 2308 2291 2287 2317 2229 2217 2142 2187 2206 2126 2148 2044 2074 2091 2099 2058 2113 2031 1991 1987 1956 1915 1887 1924 1826 1880 1838 1840 1801 1809 1841 1784 1759 1796 1730 1744 1664 1797 1751 1706 1769 1746 1717 1631 1647 1670 1730 1652 1676 1704 1723 1678 1690 1677 1702 1622 1883 1731 1563 1760 1621 1593 1648 1558 1599 1591 1497 1552 1558 1476 1586 1457 1542 1531 1356 1309 1384 1413 1321 1443 1387 1399 1471 1437 1498 1410 1405 1365 1381 1387 1277 1274 1367 1350 1260 1204 1229 1245 1213 1228 1169 1247 1227 1305 1235 1210 1143 1224 1175 1112 1127 1073 1141 1147 1050 1122 1058 1066 1096 1012 1066 1056 1036 1031 959 1069 995 990 1023 942 968 1000 1029 980 958 968 1033 934 905 977 1008 950 933 954 969 953 978 929 904 982 906 909 862 900 795 833 820 833 783 777 842 819 820 760 781 812 782 745 790 779 769 771 769 786 797 811 795 759 711 734 675 789 707 722 676 696 703 707 672 689 716 652 648 682 691 666 710 693 662 715 747 713 704 645 665 706 624 626 664 645 659 656 612 695 638 645 612 636 604 594 615 592 601 608 604 603 582 625 615 609 628 654 656 612 643 623 620 619 631 662 649 704 684 709 832 848 750 730 707 682 614 626 716 565 571 689 616 678 621 667 633 668 628 541 548 552 607 554 532 573 567 496 500 484 506 480 525 465 532 559 570 553 626 552 508 550 499 510 490 499 559 474 467 530 515 503 580 453 480 470 465 425 464 453 447 447 408 463 457 468 431 393 448 465 408 409 413 497 401 357 413 404 397 418 377 393 362 413 420 403 378 383 371 379 391 384 412 374 411 410 410 411 372 364 421 398 415 405 409 403 401 410 361 397 331 384 377 369 368 346 352 345 352 319 378 327 342 315 309 334 292 303 313 279 281 299 301 316 291 281 288 321 349 335 306 325 311 308 329 348 304 313 345 289 281 320 294 286 315 278 303 275 269 288 292 285 258 310 333 254 221 239 242 247 254 251 270 242 263 250 263 242 260 249 231 239 260 278 273 428 277 257 247 239 212 254 269 204 256 227 230 201 214 224 186 201 226 227 219 214 195 208 220 215 195 201 249 204 202 232 222 227 192 231 218 201 233 205 219 183 202 210 193 189 184 191 161 182 183 160 182 169 177 162 165 163 178 189 162 192 210 185 181 178 150 178 159 185 148 165 145 180 167 179 198 194 155 193 172 194 183 151 166 166 174 173 168 168 182 147 165 153 148 152 173 151 142 165 158 168 142 194 162 163 149 137 129 169 142 136 148 164 149 167 149 127 162 145 152 155 131 140 138 154 147 183 146 142 140 140 151 128 158 162 144 184 141 150 189 175 142 139 164 152 170 149 133 156 141 149 143 160 173 145 146 116 133 140 134 143 136 158 128 118 151 124 130 117 141 122 125 145 122 132 152 129 144 108 116 106 127 131 129 101 109 148 111 106 110 111 97 122 126 104 114 118 108 117 113 117 122 103 114 116 130 114 115 121 118 119 130 149 120 119 118 111 135 121 134 111 97 118 119 96 92 115 94 105 95 123 87 103 116 93 112 107 127 96 110 95 123 105 97 120 96 114 105 113 115 98 108 99 109 130 109 90 106 97 94 102 113 131 98 107 109 99 95 107 102 111 103 126 93 94 93 102 98 103 84 109 99 101 85 78 80 91 98 84 83 86 95 94 89 85 82 81 82 80 69 61 98 69 89 81 64 92 66 81 58 60 68 80 82 66 55 81 63 67 85 62 73 65 69 62 80 56 78 67 57 98 58 83 66 73 54 64 76 65 96 64 86 71 88 86 76 59 69 51 51 53 99 65 72 83 77 70 67 67 53 66 86 72 62 61 56 53 70 74 60 56 75 78 87 81 78 84 79 62 81 65 71 75 64 56 51 56 77 70 58 55 73 66 66 62 58 51 63 53 61 54 60 57 58 47 59 55 56 52 53 48 53 48 43 47 58 57 42 38 53 50 48 50 53 58 39 59 50 44 53 48 50 66 48 68 51 45 47 41 38 43 47 58 39 46 38 48 33 53 43 50 44 52 34 42 44 38 38 50 47 50 48 58 50 47 46 34 44 46 38 37 42 43 47 53 47 40 50 54 50 36 43 46 45 58 43 50 65 57 65 61 67 73 63 63 64 74 59 46 56 58 60 55 53 48 50 40 55 54 54 40 41 49 57 63 54 40 47 52 42 49 43 44 55 42 52 37 48 43 34 45 48 46 42 48 39 43 48 41 41 27 43 34 35 30 43 36 36 43 46 37 45 28 32 37 39 27 41 38 32 36 39 38 31 24 38 33 29 25 27 40 25 32 28 44 38 38 29 41 41 37 41 38 38 33 32 40 29 27 39 25 28 39 33 42 33 30 36 33 31 39 39 26 33 28 32 31 30 37 34 25 31 33 29 30 44 41 28 28 30 25 27 26 27 19 34 32 32 37 23 25 24 27 26 23 36 22 22 23 19 23 35 34 35 29 27 31 17 35 30 18 22 27 26 25 22 19 26 20 31 33 23 24 31 21 21 27 39 23 31 23 36 23 34 23 23 34 31 25 27 24 27 26 37 29 29 27 38 31 32 38 33 34 40 16 39 31 25 21 39 29 29 36 26 28 25 32 16 26 29 24 40 29 44 34 37 34 36 26 28 26 38 28 25 26 25 20 27 13 24 21 33 22 29 36 33 25 30 18 29 21 35 22 26 30 32 28 29 23 16 24 39 29 32 28 24 43 69 147 146 168 133 95 107 114 47 22 14 21 18 19 28 18 29 26 28 29 26 30 27 23 31 34 24 20 23 18 29 19 23 32 21 32 33 45 28 39 37 34 38 26 18 25 21 14 20 21 20 19 23 19 25 21 30 19 19 19 19 19 17 19 18 14 29 18 20 24 20 26 21 18 19 16 27 31 23 35 20 19 20 26 27 13 20 13 20 20 21 27 24 16 17 23 21 21 21 29 20 31 19 12 27 14 22 17 16 20 18 15 15 16 20 23 21 15 21 17 14 14 20 16 17 15 29 34 8 13 21 18 22 21 20 16 19 13 13 15 18 28 13 15 14 14 19 13 30 22 21 20 17 13 17 16 15 23 19 18 20 12 21 26 16 26 21 16 20 21 16 24 25 24 23 13 17 28 25 18 40 25 30 19 21 25 13 18 17 18 16 17 33 27 23 26 14 15 13 18 26 18 9 17 22 26 15 11 20 18 21 22 22 20 13 23 16 17 18 20 11 15 24 20 16 19 19 16 21 15 24 22 15 17 14 20 14 15 18 21 15 19 12 17 21 15 24 20 16 16 9 20 17 22 18 16 18 21 24 11 14 11 15 14 17 19 8 25 17 9 13 29 19 17 15 23 17 15 17 14 26 18 20 19 18 20 16 21 16 18 22 14 17 15 20 11 28 21 11 23 20 18 21 18 17 20 16 21 18 16 19 17 21 25 29 23 16 10 15 24 14 4 16 
];
B = [
0 0 0
 150789 42966 107823
 71648 20077 51571
 253044 83549 169495
 158953 47096 111857
 91937 26572 65365
 248239 84754 163485
 194897 60533 134364
 110517 33107 77410
 335149 112184 222965
 350220 109756 240464
 62720 18245 44475
 1003126 340784 662342
 132108 41964 90144
 42008 12716 29292
 224011 87856 136155
 71328 26126 45202
 22203 7249 14954
 245648 97560 148088
 20335 6494 13841
 20926 7195 13731
 4777 1644 3133
 110 32 78
 4754 1713 3041
 364066 147722 216344
 24255 8112 16143
 31189 11509 19680
 378879 155795 223084
 22195 8411 13784
 46953 17831 29122
 598468 235819 362649
 43462 16805 26657
 77877 30851 47026
 422983 181822 241161
 293835 126638 167197
 490740 216226 274514
 884604 388252 496352
 728113 297488 430625
 451429 194830 256599
 1030151 461106 569045
 409394 161830 247564
 27783 10950 16833
 929197 407793 521404
 14701 5848 8853
 26263 10520 15743
 1264508 576185 688323
 27088 11049 16039
 333585 132666 200919
 1723900 850614 873286
 331642 135846 195796
 9 4 5
 12248627 6344749 5903878
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
59 92 0 1
75 20 0 1
118 24 1 2
170 34 0 0
102 42 1 0
110 40 42 1
297 72 75 7
1448 93 97 25
8408 97 126 49
37000 136 187 80
92645 192 225 129
203631 216 326 212
399732 322 454 300
753795 429 620 439
1146645 535 831 652
1411275 834 1114 1026
1314270 1141 1531 1445
990473 1676 1957 1914
634554 2637 2549 2530
342366 3671 3073 3050
153585 4834 3706 3595
44280 6141 3969 3946
9979 6366 4174 4022
7113 5425 4219 4192
6407 5412 4374 4447
6309 5847 4451 4521
6552 5256 4473 4606
6052 5254 4747 4692
6037 5723 5142 4945
6107 5649 5365 5436
6206 6093 5724 5704
6987 6615 6029 6194
7725 7253 6477 6424
8310 7654 7053 6978
8596 8227 7711 7802
9297 8951 8150 8415
10056 9500 9180 9094
10839 10622 10177 10042
11465 11371 11094 11434
12508 12552 12232 12312
13882 13995 13613 13630
15370 15358 15398 15427
17288 17160 16995 17144
19304 19370 19427 19300
21445 21447 21540 21502
24070 24511 24515 24739
27257 27482 27425 27427
30193 30282 30126 30170
33134 33528 33165 33368
36885 36424 36253 36037
39537 39249 39274 39541
41907 41512 41143 41808
44099 44022 43606 43561
45909 46037 45976 45894
48678 47889 48384 47856
49151 49815 49683 49427
52451 52458 52348 52208
56101 55188 55141 54931
57850 57163 57243 57314
60227 59442 60282 59645
62403 62378 62296 61915
62691 62604 62665 62595
60591 59659 60666 60313
53051 53009 52814 53574
39810 40258 40751 39922
23298 23852 23919 23023
11550 11942 12042 11400
7904 7818 7802 7245
7043 6383 6540 6133
5915 5982 6872 5450
4360 4490 4380 4622
3151 2646 2988 3240
264 267 232 238
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
