A = [
349581 381731 1104654 310213 354985 312992 312287 320229 313543 297428 297563 305063 307589 304921 304549 301817 300728 303878 298915 297147 299349 296506 294832 294640 293621 312447 313589 313567 330033 315457 314952 313811 298754 298506 296089 295418 292964 289919 288478 286026 283337 283978 281600 279741 280599 276357 273786 271598 268112 265521 262417 260138 260337 257113 254158 253449 250358 247034 245900 243350 239935 238514 235027 232466 229562 228255 226275 223363 221587 218349 215173 213079 210408 207575 205460 202566 200068 197659 194297 191307 188764 186473 184373 181195 179780 176393 174590 171625 168741 167551 164226 162718 159976 157469 155983 154015 151467 149888 147087 145391 144030 141898 138942 137398 136061 133759 132460 130440 128694 126165 124692 123496 121511 120659 118654 116557 115448 114123 112003 110849 108948 108208 106752 105027 103223 102372 101055 100318 98468 97259 95847 94839 93771 92110 90908 90006 88546 87552 85998 85003 84122 82244 82022 81065 80513 78731 78076 76894 76307 75603 74283 73235 72838 71969 70666 70063 68317 68018 67460 65844 65421 65013 63962 63121 62505 61604 60891 59972 59499 58453 58186 57070 56700 55734 54993 54033 53525 53301 52016 51549 51291 50517 49957 49237 48705 48101 47259 46922 46404 46080 45234 45008 44034 43744 43357 42709 42431 42113 41484 40840 40284 39734 39343 38927 38349 37714 37737 37176 36743 36804 36532 35447 35351 34729 34389 37514 33978 33947 33403 32500 32358 31637 31378 31767 30805 30386 30030 29779 29672 29179 28668 28234 27921 27812 27538 27534 29310 27965 26794 26134 26237 26198 25545 25400 25326 25031 24497 23934 23893 23471 23319 22967 23060 22710 27238 22393 22307 21967 21480 21495 21098 20699 20516 20371 20103 19835 19569 19676 19175 19082 18808 18960 18542 18157 18119 18201 17922 17633 17696 17489 17433 17295 17126 16638 16923 16479 16300 15906 16066 15826 15687 15585 15509 15278 15296 14936 14945 14779 14753 14327 14206 14012 14126 14226 13761 13704 13763 13343 13340 13100 13029 13013 12670 12729 12581 12352 12342 12074 12015 11951 11794 11705 11611 11462 11232 11308 11293 11047 10825 10846 10621 10733 10762 10598 10522 10283 10263 10169 10023 10004 10021 9909 9999 9687 9565 9680 9456 9395 9199 9272 9122 9259 9087 8879 8822 8881 9191 8520 8352 8420 8258 8271 8247 8030 7921 8140 8109 7866 7830 7775 7595 7695 7619 7476 7359 7615 7300 7147 7346 6984 6925 6913 6951 6900 6819 6901 6763 6763 6680 6603 6487 6502 6483 6471 6443 6330 6216 6165 6177 6064 6096 6002 5856 5739 5872 5806 5703 5673 5571 5652 5631 5625 5529 5547 5447 5324 5314 5304 5214 5153 5180 5091 5101 4989 4986 5006 5027 4979 5015 4861 4724 4714 4595 4714 4686 4593 4550 4516 4617 4416 4276 4336 4229 4220 4292 4183 4084 4201 4098 4072 4192 4069 4105 4036 3956 3952 3926 3960 3838 3932 3860 3774 3767 3683 3734 3740 3763 3631 3658 3469 3641 3396 3546 3432 3338 3456 3358 3459 3431 3296 3314 3302 3215 3371 3236 3196 3178 3095 3187 3276 3097 3129 3021 3093 2997 3051 2996 2952 2939 2892 2969 2926 2962 2857 2836 2921 2790 2760 2775 2779 2785 2805 2620 2725 2693 2677 2666 2801 2591 2697 2617 2513 2554 2619 2545 2470 2506 2497 2435 2416 2467 2481 2486 2362 2435 2351 2395 2396 2386 2356 2374 2380 2294 2352 2357 2452 2263 2467 2458 2216 2412 2191 2314 2288 2179 2283 2141 2212 2141 2137 2058 2170 2179 2080 2004 1953 2047 2028 1977 1942 1997 1970 1957 1924 1948 1980 1932 1995 1869 1832 1923 1917 1973 1797 1820 1809 1848 1844 1796 1790 1745 1861 1786 1722 1731 1689 1702 1685 1736 1668 1621 1647 1710 1644 1659 1622 1698 1772 1644 1688 1684 1654 1577 1577 1528 1607 1598 1546 1579 1516 1469 1486 1566 1483 1482 1457 1539 1419 1482 1443 1517 1381 1380 1415 1439 1299 1361 1371 1330 1389 1477 1302 1362 1325 1310 1320 1313 1316 1376 1378 1318 1231 1210 1232 1237 1290 1273 1270 1200 1163 1241 1165 1268 1161 1148 1188 1223 1180 1205 1202 1271 1134 1235 1174 1156 1151 1141 1091 1141 1069 1074 1061 1090 1147 1124 1125 1156 1079 1088 1082 1062 1071 1021 1003 1099 952 1025 1019 1029 1005 963 1019 930 1011 980 910 976 894 1003 964 925 988 1046 1011 971 1019 987 1031 933 925 1069 1007 997 951 966 1017 964 973 890 1017 909 998 927 1027 933 1011 1047 996 900 862 868 925 879 843 912 1010 915 898 910 886 818 841 833 899 811 863 819 849 741 816 824 820 743 798 796 755 799 807 799 797 755 781 818 801 777 754 806 838 830 755 719 769 737 716 681 765 808 836 662 681 707 715 702 723 771 680 659 689 687 703 708 676 642 636 605 641 657 662 659 668 625 648 700 641 642 676 576 622 580 654 601 656 579 583 580 607 591 564 615 613 565 606 574 565 584 625 643 619 630 629 608 654 589 557 594 580 583 612 529 611 518 572 564 574 521 575 518 510 519 512 502 488 531 456 498 509 454 502 491 476 506 464 436 436 511 468 461 470 449 466 453 485 470 459 436 446 447 424 458 441 408 406 455 467 472 442 482 462 435 471 435 419 457 426 419 374 410 468 408 431 449 421 368 385 408 362 393 420 403 382 427 391 388 422 346 366 425 378 384 362 379 364 341 359 345 331 339 334 342 329 343 367 357 328 335 343 332 367 332 317 365 354 339 328 351 330 334 353 309 341 312 294 344 334 312 329 306 342 330 307 319 324 319 313 319 317 298 307 339 293 299 318 286 311 290 272 306 317 315 287 279 314 276 298 298 276 318 246 282 273 309 285 309 272 246 267 296 256 278 247 252 258 250 250 264 253 267 291 291 261 258 282 248 244 265 274 245 251 257 264 234 254 243 275 261 247 244 238 267 257 273 233 268 239 225 267 251 237 281 263 247 240 216 241 239 238 261 260 262 270 238 255 246 233 238 247 238 211 230 214 219 250 227 206 210 219 234 220 257 226 255 249 234 207 211 223 229 215 214 204 236 213 195 223 227 218 233 221 227 225 211 216 191 191 212 245 214 214 207 174 192 202 190 207 198 184 200 189 239 220 223 229 220 209 217 191 188 214 191 181 201 245 218 188 214 175 188 196 206 205 176 208 198 214 192 175 203 164 156 203 173 199 175 202 175 170 183 209 173 197 181 146 171 162 192 169 183 183 164 167 174 165 184 163 170 181 175 188 175 179 170 159 189 152 188 190 169 160 167 154 179 154 189 169 147 142 184 152 152 161 157 153 144 153 176 168 151 157 162 155 155 165 154 134 163 143 143 172 139 133 105 166 161 151 120 125 131 136 147 135 146 134 150 139 102 117 131 118 138 138 113 118 150 134 123 116 143 139 161 138 139 127 114 142 134 120 114 136 128 144 140 138 133 138 130 129 124 128 111 113 122 120 141 141 135 123 115 120 118 141 138 131 115 130 115 111 114 128 114 129 137 132 127 122 126 119 130 126 105 129 112 123 125 112 118 114 121 140 102 87 98 123 94 106 91 118 98 107 108 111 110 96 92 101 92 125 80 92 104 111 103 90 90 87 105 117 88 96 100 81 94 87 109 93 112 121 112 91 107 101 112 110 89 101 101 99 117 99 101 87 86 78 97 90 108 113 86 111 89 88 87 100 89 91 83 85 98 90 85 96 84 97 106 89 102 103 99 74 109 107 84 92 103 102 119 83 83 100 90 78 73 77 93 84 95 84 95 81 77 79 101 83 102 65 83 77 97 82 88 87 90 99 87 116 93 113 83 68 83 90 74 80 84 94 78 98 64 78 99 86 82 77 63 74 77 64 74 76 68 76 74 72 79 75 75 84 86 78 59 67 66 102 92 69 66 73 73 68 82 65 66 67 81 77 72 79 73 73 68 63 84 88 68 57 63 56 52 74 52 77 69 74 58 68 73 59 58 74 56 77 80 58 74 57 67 53 62 75 86 69 70 62 60 58 58 53 49 65 61 72 60 63 60 60 62 56 60 69 79 68 61 61 58 57 53 66 66 68 45 60 65 44 71 62 53 49 58 58 68 65 53 52 71 63 72 59 61 62 75 53 60 54 58 74 58 73 63 58 48 64 54 62 72 61 80 64 45 53 46 43 63 60 59 50 63 43 52 66 63 45 67 73 56 58 48 46 65 57 49 50 59 71 70 60 42 55 55 56 52 54 64 52 58 66 63 57 59 50 57 57 45 53 50 61 48 51 47 43 54 44 62 61 52 48 77 59 60 62 67 76 74 81 74 81 73 76 79 62 71 54 80 69 68 74 70 86 78 75 67 68 80 66 62 61 72 59 65 60 89 75 87 81 71 71 71 73 95 73 128 112 145 78 86 69 66 61 53 45 48 39 54 57 57 47 66 58 58 57 54 57 55 41 69 49 52 55 46 30 48 59 47 41 47 63 67 52 59 49 50 55 45 39 47 52 44 58 58 48 51 44 36 59 56 53 67 50 43 51 57 56 46 40 42 48 38 38 50 50 48 60 43 25 26 45 42 30 38 35 34 54 45 39 36 46 34 47 49 34 39 44 40 47 52 40 46 44 54 37 49 52 43 43 40 33 39 31 34 42 41 44 58 46 49 34 29 39 37 28 44 29 35 41 49 39 38 38 40 42 37 36 39 43 39 42 32 35 35 34 42 48 29 32 35 27 36 34 45 51 47 41 39 42 37 26 47 43 27 41 38 44 35 39 44 40 41 39 29 39 48 46 41 31 42 46 40 35 40 38 38 55 37 44 36 40 45 31 47 29 29 42 43 48 34 28 43 43 36 35 46 33 39 35 33 37 37 37 31 38 30 32 40 39 37 33 38 43 31 36 48 35 38 36 33 34 37 31 42 34 25 34 42 26 37 29 39 33 30 29 26 37 35 31 31 33 34 38 28 36 34 27 26 22 25 22 35 36 36 41 39 33 36 34 36 36 29 34 43 32 27 28 41 42 40 41 39 37 42 44 36 31 33 39 32 37 29 43 42 30 30 27 37 31 34 29 30 36 30 30 38 33 24 29 31 38 33 35 42 27 41 29 31 33 31 35 30 29 34 33 33 41 
];
B = [
0 0 0
 93463 26601 66862
 94096 27473 66623
 134824 44853 89971
 81403 23764 57639
 92575 28792 63783
 106715 35351 71364
 115258 37076 78182
 116952 38099 78853
 183296 65525 117771
 186264 71471 114793
 169282 64355 104927
 329613 147912 181701
 86504 25253 61251
 80677 29522 51155
 69396 24124 45272
 42169 14850 27319
 57751 23526 34225
 35353 12084 23269
 56301 20264 36037
 39882 14247 25635
 76931 29060 47871
 64911 23055 41856
 90000 37473 52527
 78320 26742 51578
 116219 41435 74784
 80455 35159 45296
 227161 79788 147373
 83185 35433 47752
 193330 92773 100557
 63995 26117 37878
 50343 19553 30790
 67642 29960 37682
 85983 34341 51642
 44662 18616 26046
 73185 32788 40397
 46061 20659 25402
 48511 20791 27720
 55353 25973 29380
 96940 41883 55057
 33582 14459 19123
 84546 41716 42830
 39174 16741 22433
 40578 17124 23454
 134566 65691 68875
 34966 14793 20173
 42988 19331 23657
 70026 32737 37289
 115616 47856 67760
 73334 35000 38334
 41048 17818 23230
 43923 19777 24146
 74401 34954 39447
 35733 15058 20675
 157656 69184 88472
 73933 35431 38502
 33636 13743 19893
 45586 20676 24910
 145635 69061 76574
 91907 38208 53699
 14553628 8069924 6483704
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
51 46 0 0
46 7 0 1
133 20 0 0
110 27 0 2
67 20 0 2
93 34 3 4
563 59 8 5
6136 74 23 9
53456 111 50 19
239424 137 91 49
523612 174 123 77
835267 235 157 100
1006193 305 236 159
1099009 357 314 248
1057134 457 375 291
974769 574 518 442
791659 760 675 608
589923 942 916 837
433955 1186 1067 1031
262247 1449 1318 1235
103467 1894 1457 1395
22211 2231 1619 1541
6089 2503 1593 1516
4983 2513 1751 1736
4470 2585 1719 1943
4196 3162 1697 2004
4897 2819 1913 1981
3522 2905 1952 1927
3612 2972 2084 2038
3052 2717 2405 2162
3251 3011 2324 2357
3765 3496 2521 2524
3969 3802 2581 2557
4607 4257 2965 2950
4542 4245 3137 3223
4439 4265 3479 3283
4940 4478 3741 3883
5149 4771 4287 4223
5081 4987 4461 4623
5226 5089 4885 4823
5858 5700 5352 5397
6405 6313 6106 6037
6746 6692 6770 6684
7719 7536 7527 7436
8531 8544 8583 8481
9613 9731 9527 10284
11038 10978 10987 10636
11837 11802 11733 11776
13325 13111 13365 13155
14796 14062 14261 14120
15650 15411 15663 15549
16756 16392 16537 16146
17786 18100 17500 17604
18641 18299 18536 18743
20279 19757 20018 19801
20793 20789 20758 20551
21418 21779 22200 21096
23997 23354 23314 22680
24474 23872 24322 23822
24923 24734 25000 25213
26761 27646 26348 26304
26817 26561 27136 26221
26654 25815 26448 26321
23916 23777 23431 23786
17978 18403 18817 17934
12006 12713 11966 12221
8969 9172 9126 9211
8294 8331 7852 7093
7948 6804 6924 6490
6241 6288 6597 5791
5296 4836 4528 5079
4406 3716 3824 3923
318 283 323 325
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
