A = [
576452 705708 840652 508891 932888 616164 605212 884654 715495 852956 593306 615921 800711 641549 662662 593385 670145 662428 645789 642794 605368 680084 638494 618754 643225 595953 594885 602637 634959 615232 600097 627716 616601 564628 548643 599378 669801 592115 631238 665146 578354 559239 535621 577111 537778 552252 563494 538409 550025 514427 514746 540056 514116 531713 512258 490980 513303 473861 477012 466816 462887 479132 453657 463689 455221 439573 453093 433660 441640 428567 436614 432852 411614 417683 405089 412726 447978 443053 427689 432604 425291 406591 396246 389325 377016 383320 371411 352650 346006 341501 340437 339808 332276 328799 326268 321235 317490 313019 307708 301119 298650 297352 294945 293413 287785 286748 282369 277741 275629 271680 269801 265964 262143 259343 255297 254677 253887 252138 251538 248450 247096 243739 241272 239073 233839 233357 228622 227440 224863 220823 218768 215129 213028 211672 209299 209217 205817 202816 200833 198986 197918 194465 192428 189822 188129 185453 182979 181121 179661 177842 174604 173076 171003 168879 167144 165046 164548 162339 159556 158969 156397 155299 153336 150906 151263 149397 147587 145821 144168 143299 140451 140295 138420 137577 136617 134038 133747 131079 131441 129863 128577 127885 125774 124149 123346 121700 121451 118781 118555 118104 115017 114454 112475 112089 110432 109752 108843 106625 105607 104612 103200 102992 101940 103239 100068 99545 99398 96583 96413 95148 94770 95016 93614 92313 92039 90011 88603 87481 87173 86025 85455 84453 83556 84646 81790 80711 80316 79477 79866 78018 77647 76945 76282 75800 75089 74397 74471 72835 72938 72191 72291 71233 70426 69902 68804 68833 68557 67688 67085 67416 66568 66291 65482 65015 64828 63832 63795 63069 63647 62492 61744 61993 60855 60966 59967 59588 59295 59041 58550 58545 57719 57351 57191 56295 55801 55589 55468 55284 55304 54024 54112 53279 53625 52684 52278 51981 52093 50839 51109 51299 50437 49662 49420 49360 49385 48268 49165 47763 47394 47485 46879 47213 46640 46296 46031 46553 45310 44540 44274 44185 43637 43784 44155 43431 43195 42630 42531 42144 42027 41548 41162 41041 40638 41440 40181 40601 40059 39785 39509 38587 38566 38652 38595 38158 37485 37297 36992 36827 36944 36394 36289 35856 36070 35728 35500 35301 35036 34787 34645 34038 34224 34172 34136 33753 33807 33276 33371 32610 32664 32605 32220 31950 32120 31721 31788 31198 31533 31093 30681 30907 30658 30661 30630 29776 29745 29778 29207 29511 28777 29252 28978 28726 28608 28385 28254 28187 28102 27700 27393 27611 27146 27282 26938 26771 26921 26580 26285 25964 26171 25760 25805 25649 25472 25302 25404 25353 25060 24756 24723 24742 24485 24356 23986 24154 24032 23839 23630 23403 24017 23061 23269 22831 23166 22592 22945 22653 22686 22711 22301 23090 22267 21971 21950 21936 21655 22428 21621 22660 21164 21158 21123 20684 20844 21151 20498 20363 20328 21023 20067 20322 20078 20146 19714 19766 19570 19596 19619 19567 19143 19368 18780 18811 19018 18688 18512 18546 18350 18841 18323 18074 18316 18531 17918 17858 18005 17740 17880 17668 17808 17368 17095 17069 17225 16822 16753 16781 16857 16440 16371 16368 16411 16196 16023 17109 15975 16026 15712 15759 15843 15653 15461 15367 15267 15435 15193 15822 15862 14912 14942 14888 14725 15047 14549 14575 14650 14628 15279 14511 14594 14345 14510 14000 14235 13966 13784 13584 13714 13869 13505 13623 13232 13402 13111 13047 12924 12827 12931 13016 12688 12696 12588 12782 12358 12532 12359 12344 12256 12295 12361 12117 11941 12229 11856 11777 12260 12536 11688 12589 11641 11630 11587 11315 11430 11301 11276 11527 11295 11307 10953 10753 11194 10720 10775 10932 10740 10698 10676 10520 10252 10783 10548 10296 10338 10358 10217 10169 10098 9873 10271 10218 9926 9875 9829 10003 10010 9782 9957 9707 9346 9400 9365 9715 9873 9602 9219 9519 10314 9030 8934 11098 9116 9314 8860 9291 8891 8816 8658 9184 8757 8734 8645 8653 8468 8700 8591 8409 8265 8273 8345 8254 8182 8118 8085 8662 8036 8155 7964 7884 7998 7788 7752 7686 7766 7793 7558 7531 7395 7471 8255 7455 7222 7447 7268 7433 7514 7272 7330 7117 7145 7105 7153 6868 7040 6931 6966 6866 6821 6894 6802 6839 6914 6600 6864 6596 6557 6475 6443 6581 6299 6503 6349 6417 6251 6279 6237 6320 6194 6366 6149 6308 6201 6004 6373 6146 6053 5892 6024 5829 6110 5935 5862 5680 5734 5739 6090 5779 7540 5746 5578 5749 5592 5749 5690 5821 5506 5491 5407 5358 5611 5453 5521 5278 5246 5351 5217 5186 5769 5129 5091 4944 5046 5096 5026 5034 5010 4962 4852 5006 4879 4979 4787 4851 4849 4618 4595 4723 4677 4678 4585 4507 4557 4527 4540 4624 4560 4417 4456 4440 4386 4512 4403 4387 4408 4273 4322 4224 4388 4371 4277 4195 4001 4165 4188 4110 4225 4041 3924 4081 3980 3914 4047 3913 3924 3972 3939 3871 3900 3718 3777 3928 3786 3722 3799 3579 3970 3795 3769 3729 3616 3773 3656 3729 3640 3677 3648 3549 3458 3520 3442 3470 3486 3349 3268 3489 3378 3334 3361 3414 3361 3456 3337 3333 3314 3242 3348 3177 3243 3165 3229 3124 3143 3142 3066 3100 3045 3032 3100 3077 3097 2947 3019 2863 3013 2939 2958 2793 2831 2827 2932 2952 2906 2810 2838 2868 2798 2829 2681 2708 2778 2766 2705 2792 2736 2618 2661 2729 2764 2610 2523 2580 2513 2506 2598 2537 2537 2559 2491 2486 2433 2523 2457 2410 2338 2437 2390 2436 2445 2480 2438 2406 2258 2380 2290 2337 2313 2410 2282 2323 2270 2216 2239 2168 2155 2288 2244 2179 2220 2185 2175 2103 2154 2101 2035 2085 2025 2141 2152 2159 1926 2002 2004 1989 2057 2010 1933 1997 1893 2032 1941 1955 1820 1900 1952 1853 1919 1912 1827 1843 1906 1913 1852 1773 1876 1815 1829 1825 1889 1751 1772 1782 1725 1726 1859 1711 1759 1732 1688 1703 1652 1711 1806 1713 1625 1593 1716 1658 1623 1667 1633 1607 1634 1670 1612 1591 1590 1538 1691 1514 1496 1485 1552 1476 1521 1487 1596 1520 1489 1524 1433 1501 1466 1448 1443 1430 1490 1391 1429 1443 1397 1434 1398 1397 1432 1360 1358 1334 1372 1331 1374 1391 1241 1321 1287 1341 1227 1338 1224 1346 1270 1307 1282 1177 1279 1288 1261 1333 1196 1259 1261 1240 1296 1244 1222 1212 1168 1215 1155 1237 1171 1165 1162 1185 1175 1153 1128 1094 1129 1070 1142 1122 1233 1231 1476 1341 1369 1315 1478 1637 1686 1603 1505 1739 1705 1844 1447 1481 1651 1452 1455 1324 1243 1280 1359 1377 1496 1386 1368 1522 1499 1178 1066 937 973 945 1047 1049 1010 1037 1030 1043 964 1010 957 958 993 973 945 986 900 942 896 936 957 926 861 916 876 928 867 888 886 870 847 849 1069 864 845 825 889 822 819 808 864 829 892 863 742 748 775 754 815 829 771 762 755 780 707 753 761 760 745 770 813 732 717 799 734 726 732 794 725 769 691 687 805 794 741 750 711 670 665 701 680 685 684 658 644 621 651 658 649 647 647 626 692 640 680 627 682 696 668 637 589 606 2459 590 646 555 600 668 645 636 604 551 648 609 902 614 574 540 569 577 667 545 583 564 527 568 581 503 580 530 576 510 552 500 496 498 627 539 474 483 488 532 711 516 484 547 441 477 610 511 488 457 526 495 514 469 475 456 454 431 485 446 472 465 469 444 434 435 439 529 457 454 408 418 405 412 491 456 387 429 416 419 445 458 430 443 446 408 378 438 404 408 418 425 406 381 391 368 382 376 350 389 351 399 381 338 403 381 378 375 421 353 360 375 373 350 393 337 330 365 384 363 329 411 350 359 350 346 281 356 345 333 309 312 304 323 338 314 341 283 321 343 321 300 290 323 334 329 307 313 270 307 333 293 293 313 326 315 228 325 366 316 267 281 288 276 281 283 259 273 252 274 260 275 294 250 321 264 265 264 270 274 260 285 284 291 286 258 261 301 263 256 266 276 248 259 268 271 272 262 260 253 267 250 257 251 236 220 229 214 251 249 232 237 246 258 236 258 216 243 217 233 238 252 207 239 243 223 228 236 213 197 207 228 218 234 200 182 207 211 225 215 223 218 193 207 209 189 197 196 186 211 184 206 210 205 190 199 165 196 199 193 191 207 176 187 171 167 216 206 179 199 179 209 194 206 181 162 159 168 155 157 163 151 169 161 182 168 177 186 168 137 136 177 163 175 162 150 184 179 173 168 151 184 150 150 171 174 148 136 170 180 165 137 141 154 172 145 138 147 142 141 163 144 133 152 150 136 135 142 146 131 136 121 126 138 143 138 148 108 140 135 125 121 146 139 114 123 123 119 127 121 133 132 156 126 139 124 119 130 147 121 126 115 126 107 112 126 99 117 109 100 138 118 106 123 99 129 121 100 93 118 119 103 113 92 99 110 114 121 87 101 109 89 87 107 85 99 94 95 105 103 89 108 95 88 89 91 105 84 86 95 92 111 89 116 91 105 92 92 84 84 112 97 75 88 95 83 81 83 78 87 100 89 81 80 90 74 84 92 70 75 77 72 61 67 72 79 75 77 84 80 87 70 72 67 61 71 63 83 77 86 56 83 90 69 90 71 73 70 84 98 70 65 88 65 66 60 69 54 63 77 74 72 67 56 68 54 70 70 72 62 55 56 73 69 79 71 63 66 55 76 54 59 62 56 66 60 61 60 62 64 53 56 58 53 46 53 52 47 59 48 51 60 59 56 54 52 50 58 57 45 58 56 51 55 62 40 58 56 44 54 47 39 46 60 40 41 36 63 42 57 44 45 43 47 59 44 46 41 43 53 46 48 47 40 45 55 40 32 37 50 47 50 39 53 52 39 38 43 51 45 38 65 39 43 44 34 25 48 38 50 28 48 34 36 50 34 47 41 32 45 31 32 47 38 41 36 51 31 28 38 39 38 37 34 37 41 21 31 34 34 31 41 40 31 32 36 30 41 35 32 27 35 26 28 29 37 20 23 25 28 28 28 34 36 36 34 31 29 21 23 24 21 29 33 43 30 28 22 32 24 36 29 35 28 35 22 35 19 33 39 22 20 23 25 32 20 30 18 33 16 33 31 31 23 25 29 27 23 34 22 28 31 19 30 24 20 19 24 37 27 26 28 22 24 29 24 34 28 32 25 21 22 18 32 19 29 30 25 27 24 20 31 23 27 31 24 23 26 18 18 9 31 15 33 12 24 30 26 21 22 28 19 24 21 16 22 21 28 23 10 13 22 16 25 20 25 21 16 14 19 22 17 20 24 25 22 18 15 22 15 24 20 17 24 22 16 19 26 11 16 19 12 27 13 25 15 20 15 23 13 17 13 13 15 18 18 14 20 18 21 14 20 14 16 17 13 14 21 20 23 12 12 11 13 9 17 
];
B = [
0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 263769 236439 27330
 279043 250940 28103
 278594 252056 26538
 268110 244354 23756
 351296 317044 34252
 274048 251611 22437
 284486 259309 25177
 711124 634204 76920
 278987 257784 21203
 340626 311965 28661
 588867 529917 58950
 334741 307651 27090
 527833 478531 49302
 277580 257803 19777
 334036 308200 25836
 533506 483828 49678
 326308 302049 24259
 509579 464511 45068
 322152 298847 23305
 475500 435438 40062
 318458 294816 23642
 463452 424595 38857
 329584 305866 23718
 457597 421126 36471
 319322 297101 22221
 482877 443053 39824
 437432 403591 33841
 301527 281903 19624
 426601 394411 32190
 251673 237562 14111
 32311917 30849431 1462486
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
30 6 1 3
0 3 0 0
1 18 1 0
2 35 1 2
1 21 6 3
1 72 6 3
26 73 16 31
1037 153 38 38
107398 229 69 61
644703 376 112 134
1345110 624 189 200
2242915 812 392 422
2928014 1259 793 875
3565196 2007 2137 2121
4167810 3606 4888 4837
3847104 10758 11495 11624
2874448 16550 22957 22894
1894488 22938 32509 32707
1118876 35115 42312 42851
209146 49004 58504 58981
98818 65031 73707 73912
100771 76103 87912 88130
108007 94050 102203 103109
117653 107552 115004 115257
125096 120397 124095 124701
130322 128814 129868 130057
132794 134070 132236 132221
131289 132428 130734 131487
127544 128604 126198 127205
120321 121454 118130 119637
111871 110896 110167 110915
101881 101759 101359 101238
93718 93598 92834 93290
87592 87477 86533 87530
83239 82646 82527 83041
80879 79994 80248 80445
79956 78904 78951 79145
79650 79285 78983 79290
80474 79565 80365 80347
81274 81288 80991 81458
83692 83273 82808 83124
86167 86093 85494 86119
88442 88417 87618 88428
90832 90172 90704 90048
92184 91100 90924 91994
92696 92279 92134 92246
92439 92151 91737 92706
91889 90993 91309 92360
89457 88936 88998 90028
86025 86174 86289 86799
82081 81612 81897 82163
77054 77411 77662 77485
71645 71370 71392 71541
65484 65248 65871 65783
59170 59269 59486 59363
52857 53220 53064 53398
47272 47768 47399 47578
41898 42249 41791 42107
37594 37895 37658 37913
33613 33463 33501 33638
30784 30548 30920 30736
28586 28505 28578 28721
26969 26866 26671 26749
25739 25644 25400 25457
24565 24752 24755 24664
24558 24323 24809 24523
24651 24245 24397 24889
24984 25013 24940 24864
25857 25581 25880 25823
26732 27067 26815 26816
27741 27579 27602 27945
28560 28502 28771 28450
28327 28234 28633 28311
26321 26265 26413 26218
23256 22929 23161 23361
19330 19318 19465 19545
15411 15369 15039 15592
10972 11082 11155 11153
8890 8859 8969 8991
6220 6194 6263 6323
3861 3808 3886 3845
1578 1631 1586 1532
69 75 67 60
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
