A = [
560936 501581 7107479 444354 435347 431340 427190 425751 431418 437313 500164 617682 723926 854175 1124131 1369652 1490484 1604480 1577955 1444760 1371299 1313761 1283101 1308132 1386946 2247861 2378968 2645191 3495600 2950525 2990517 2964252 2648517 2736282 2696322 2681724 2598691 2473097 2405748 2359532 2392761 2506626 2544959 2610706 2674458 2638132 2591226 2519512 2426894 2386126 2373980 2360789 2384194 2387710 2368581 2349499 2307371 2236468 2191443 2152174 2106688 2100041 2096207 2082443 2077652 2054694 2012288 1978849 1937667 1886530 1859271 1840779 1814987 1807212 1800201 1774327 1752144 1727120 1679812 1644646 1618058 1587987 1568195 1557258 1539109 1520201 1506250 1473837 1450902 1419275 1389963 1368286 1350607 1327827 1311867 1304458 1284042 1264675 1245036 1213052 1189762 1166874 1144181 1134003 1119597 1103109 1090095 1077161 1054879 1034452 1015419 991898 978589 963655 945256 937250 926545 908580 897214 886927 863852 851263 834795 818535 806811 797618 784366 772598 767906 751583 737237 727758 713133 697569 691920 677638 667993 661893 652743 642116 634714 620068 610611 601838 589119 580477 573140 562987 555518 549539 542539 531289 522959 512279 502359 495694 485816 481302 474505 465803 462655 453903 443998 439371 431095 423202 415788 409939 403411 398080 395511 387278 381941 375816 366972 360754 355996 350503 342778 339511 334074 329158 324690 318062 314106 308422 302317 296862 293635 287155 284759 279972 274696 271435 266251 262027 256254 252980 247173 244495 241512 236496 234342 230457 227012 223139 219078 216793 212718 208589 204115 202334 198818 196088 193360 189044 185674 182375 179712 175788 174591 172275 169737 167513 164208 160538 157906 155794 153734 150567 147975 146256 142984 142024 138699 136820 135084 133144 129968 127696 125470 124230 121999 120058 118153 115919 115003 111595 110975 108597 106445 105360 103006 101694 100069 99346 97275 95071 93946 92571 90932 88411 87480 85963 84742 83112 81766 80745 79329 78318 77081 75286 74566 73451 71917 70920 70350 68875 67765 67258 65740 64216 62446 62113 61926 60422 59136 58332 57419 56832 55518 54278 54216 53251 52157 51284 50633 49917 48625 48184 47697 46777 45853 45150 44666 44013 43862 42546 42192 41397 41024 40224 39430 38811 38053 38005 37054 36568 36042 35391 34997 34180 33588 33315 32836 32627 32060 31245 31085 30816 30175 29869 29249 28893 28468 28078 27599 26731 26834 26001 26097 25643 25213 25216 24841 24546 24070 23584 23310 22865 22923 22510 21943 22065 21764 21189 21019 20844 20422 20105 19817 19495 19294 18980 18660 18451 18046 18014 17592 17763 17277 16993 16795 16694 16626 16218 16164 15974 15697 15473 15354 15015 15190 14885 14250 14795 14297 14133 13637 13796 13636 13521 13159 13082 13275 13210 13077 12596 12371 12372 12251 12191 12131 12005 11724 11690 11290 11513 11509 11117 10956 10910 10787 10615 10524 10441 10299 10134 10060 10087 9680 9745 9628 9604 9539 9186 9140 9295 9137 9062 9049 9082 8838 8614 8509 8714 8648 8254 8043 8127 8088 8130 7881 8334 7818 7850 7944 7584 7700 7658 7572 7327 7155 7168 7155 7174 7137 7115 6978 7144 6746 6692 7124 6770 6672 6546 6465 6318 6486 6332 6349 6316 6292 6162 5878 6002 6064 5993 5974 5860 5593 5757 5777 5640 5692 5511 5604 5580 5463 5402 5456 5236 5294 5402 5194 5051 5171 5062 5205 5195 5115 5238 5080 4964 4889 4803 4825 4875 4784 4740 4840 4810 4673 4820 4542 4743 4612 4674 4708 4433 4585 4339 4429 4363 4308 4400 4159 4249 4072 4023 4206 4048 4114 4245 4139 4154 4169 3937 4134 3950 3948 3918 3824 4130 4012 3799 3816 3912 3804 3749 3607 3892 3854 3760 3798 3684 3777 3651 3817 3822 3607 3512 3698 3630 3548 3373 3557 3511 3463 3472 3422 3440 3257 3408 3370 3383 3366 3158 3402 3231 3392 3292 3323 3222 3177 3240 3307 3033 3113 3153 3217 3188 3090 3070 3077 3056 3027 2893 3015 2924 2789 2931 3020 3048 2791 2839 2779 2840 2881 2833 2949 2903 2946 2752 2763 2853 2696 2842 2765 2621 2837 2747 2632 2691 2614 2606 2559 2609 2690 2655 2549 2513 2514 2685 2549 2645 2492 2494 2511 2571 2468 2451 2447 2424 2484 2415 2411 2529 2360 2410 2348 2351 2417 2410 2362 2196 2284 2363 2326 2284 2290 2289 2243 2268 2235 2173 2226 2145 2235 2227 2166 2286 2230 2222 2153 2211 2182 2167 2119 2149 2148 2078 2121 2200 2026 2107 2040 2029 2135 2154 1916 1940 1969 2069 1933 1966 1946 2044 2033 1992 1962 1967 1949 1935 1885 1926 1909 1833 2012 1936 1882 2009 1861 1902 1982 1939 1924 1796 1809 1807 1889 1969 1902 1782 1919 1957 1726 1810 1842 1865 1864 1882 1845 1873 1701 1819 1879 1734 1775 1838 1791 1836 1674 1688 1738 1728 1687 1637 1750 1623 1585 1794 1591 1675 1707 1735 1590 1573 1602 1587 1687 1641 1580 1588 1576 1643 1641 1518 1518 1630 1492 1441 1493 1549 1387 1414 1523 1443 1406 1375 1442 1471 1479 1329 1419 1491 1428 1428 1380 1403 1352 1384 1390 1245 1259 1356 1356 1240 1309 1293 1383 1273 1345 1314 1291 1376 1333 1341 1318 1262 1263 1202 1404 1332 1284 1196 1233 1273 1239 1200 1172 1165 1230 1217 1313 1258 1252 1310 1235 1234 1272 1201 1167 1235 1323 1143 1358 1263 1237 1289 1194 1163 1241 1226 1216 1149 1201 1239 1162 1120 1164 1100 1272 1162 1173 1227 1229 1136 1153 1174 1093 1110 1116 1147 1156 1162 1138 1104 1191 1097 1152 1142 1155 1101 1120 1135 1074 1081 1115 1105 971 1057 988 976 1065 1006 1015 1002 1064 997 1003 968 934 1040 997 980 1081 1024 942 1004 1020 931 1045 968 1043 1040 990 916 993 1031 915 929 965 934 928 909 940 1008 1016 996 957 936 976 911 874 928 869 856 862 953 858 892 792 899 865 925 886 863 849 806 769 927 911 879 914 879 921 825 803 838 833 847 903 877 797 920 923 902 890 751 768 763 1011 785 799 649 708 725 754 707 722 736 662 765 686 696 682 744 691 731 712 738 662 726 701 736 687 680 690 686 628 709 749 733 672 721 701 699 713 662 716 689 717 716 629 715 705 680 683 653 697 659 660 694 648 621 647 648 661 674 673 641 618 578 602 630 617 609 611 605 613 595 664 599 618 628 617 636 648 592 611 608 625 573 553 561 563 594 539 558 554 573 510 521 524 494 560 520 494 550 514 549 592 563 549 538 507 502 542 555 476 527 527 547 563 571 581 624 522 573 590 526 578 574 590 550 527 518 518 555 586 599 525 559 510 569 563 583 533 555 496 545 516 511 497 556 609 517 529 468 498 516 511 507 513 460 490 480 471 511 436 477 452 484 450 416 425 459 424 369 417 386 429 467 382 387 379 397 414 388 481 407 431 443 500 373 421 428 401 394 451 422 392 353 405 385 370 385 407 366 405 377 391 401 383 408 400 445 378 377 377 394 373 395 406 374 353 440 359 430 375 379 402 392 385 451 365 354 391 435 396 377 369 384 341 357 367 369 365 361 357 358 370 393 387 409 376 399 373 349 361 334 390 402 359 382 391 326 331 361 372 323 338 328 365 338 346 339 338 351 304 326 320 349 327 330 354 354 344 357 333 292 312 303 307 304 301 261 279 253 273 273 284 276 285 280 282 286 289 312 300 318 301 323 273 319 309 282 298 265 278 319 259 300 308 263 295 312 315 311 309 250 246 265 268 247 264 217 243 257 248 249 220 226 215 236 264 252 244 250 238 211 257 257 230 246 241 235 288 225 231 255 223 237 244 254 249 248 239 266 250 231 219 251 246 249 254 266 257 252 248 267 261 260 241 286 226 233 264 245 260 263 262 272 321 253 267 233 315 291 268 251 269 290 279 269 288 252 261 265 274 285 246 239 280 232 218 247 290 240 235 245 267 246 235 240 227 259 234 247 229 307 257 272 240 194 231 261 254 221 200 209 175 229 196 181 206 198 233 214 233 229 220 246 184 201 206 214 194 202 166 211 207 216 194 184 217 191 193 208 185 218 207 150 211 207 210 189 193 165 227 212 222 175 207 184 201 222 164 155 205 191 208 185 188 210 213 169 214 173 209 210 180 179 180 182 178 170 147 204 184 202 147 177 138 162 198 181 185 193 175 167 166 180 197 208 187 180 155 153 202 188 201 182 184 218 168 195 178 197 219 180 173 178 186 183 177 185 182 190 193 203 190 179 180 172 204 147 198 167 209 149 191 170 148 197 223 200 178 190 205 183 162 173 217 176 192 193 319 177 171 163 157 176 172 216 161 202 205 189 182 184 198 164 210 163 162 169 188 164 162 225 145 163 168 166 176 132 160 164 170 186 167 123 161 167 148 156 112 138 142 145 137 156 157 150 156 142 127 130 138 127 112 124 124 137 126 112 143 129 105 111 125 147 135 133 173 131 132 163 136 143 114 114 136 137 148 145 138 129 164 137 154 147 164 147 168 136 128 124 116 123 120 129 143 140 132 117 117 117 128 125 118 146 124 115 171 154 123 127 98 143 121 166 132 141 143 144 178 154 167 136 139 152 162 146 166 176 174 159 163 191 171 161 197 134 178 176 153 181 147 182 150 162 152 164 168 198 141 186 169 194 182 210 189 172 191 203 187 194 189 187 167 159 160 178 144 145 141 131 126 108 112 135 130 109 134 124 160 129 112 97 152 104 106 125 112 119 113 123 154 118 103 108 132 133 105 120 142 116 108 106 132 96 124 101 96 114 101 90 122 109 130 115 94 117 119 110 123 100 95 90 98 96 120 122 105 103 92 93 107 116 136 113 114 99 115 109 118 120 102 102 97 117 83 126 113 108 127 99 93 131 112 69 94 68 72 107 75 81 87 82 77 82 98 71 90 98 84 73 105 96 84 69 69 79 89 99 80 77 111 83 70 64 101 82 74 80 99 102 68 98 100 74 78 102 94 72 96 87 62 85 75 96 81 88 78 76 84 78 99 88 99 104 85 68 82 75 93 82 76 84 88 96 64 89 82 88 90 80 49 109 74 80 68 72 73 60 93 69 81 87 94 61 77 79 80 88 78 83 89 57 97 71 87 71 86 63 63 95 94 81 74 70 95 83 92 79 66 91 68 52 71 52 72 69 151 71 64 75 68 65 67 62 73 44 62 46 56 55 55 48 46 47 63 68 51 47 55 46 62 51 52 52 34 45 28 35 48 42 46 40 40 31 29 34 36 32 32 76 28 33 40 46 43 65 62 50 54 62 65 58 50 56 56 66 47 50 45 51 71 41 45 45 52 59 49 45 39 56 50 33 55 59 44 50 45 62 38 46 45 41 36 42 41 29 54 41 35 41 
];
B = [
0 0 0
 123374 64341 59033
 107759 62031 45728
 141284 89284 52000
 118131 71219 46912
 114379 70850 43529
 118770 74748 44022
 144934 90354 54580
 117090 75287 41803
 173938 115012 58926
 202926 131341 71585
 133902 94374 39528
 399623 273363 126260
 112182 82715 29467
 105019 78543 26476
 101885 67062 34823
 49112 35012 14100
 78605 55211 23394
 49265 36478 12787
 57835 44377 13458
 52417 39150 13267
 70441 54426 16015
 69924 52544 17380
 110330 81115 29215
 79949 61415 18534
 122336 95214 27122
 102623 78859 23764
 232558 183941 48617
 108049 87924 20125
 348397 248754 99643
 118902 97034 21868
 82264 66223 16041
 133003 105856 27147
 144981 119682 25299
 87974 74831 13143
 144444 115835 28609
 68966 59376 9590
 79988 69350 10638
 105691 85646 20045
 141513 120944 20569
 65032 57082 7950
 137531 114013 23518
 92486 81771 10715
 62978 54942 8036
 271086 218659 52427
 83376 73171 10205
 91755 81240 10515
 160152 136109 24043
 173699 146590 27109
 169043 148410 20633
 126822 110462 16360
 93661 84602 9059
 185538 164118 21420
 99715 86603 13112
 324235 290981 33254
 155256 135099 20157
 113208 100091 13117
 130450 119771 10679
 221250 186153 35097
 394202 365028 29174
 125459887 117830838 7629049
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
35 278 7 2
4 48 0 2
11 84 0 5
24 126 3 3
16 118 5 3
36 117 15 10
2819 201 46 32
31420 231 587 144
470465 300 1939 520
1586193 419 2727 1050
2414564 532 3307 1603
3197810 857 4395 2782
3661032 1540 6163 4796
3991941 2771 10119 8765
3674450 4833 16423 15388
3347252 8662 26961 26194
2557653 14701 40004 40007
1538807 23065 55682 55277
709226 35931 73036 73699
286304 54869 92128 92161
152246 77532 110820 110933
141961 104716 132905 133062
162785 136004 159179 159803
193081 170757 188001 188290
225819 209266 223302 221897
267871 253203 261194 260779
310268 298294 305763 305670
358454 348189 353852 353399
408132 400156 404265 403691
459675 451699 455571 456939
512389 504492 507285 506617
561458 551905 554083 554216
605106 595641 597850 599930
644074 640246 638870 640679
679335 675541 677032 676922
709865 710499 708264 709773
734745 735510 735328 735838
757984 760500 758480 761762
777961 781033 778119 778952
794876 798547 797399 801169
812426 815963 814578 813865
827433 832691 828122 830351
835963 841002 838447 838752
838667 845651 842869 842243
833722 837734 835695 837811
827722 830462 828288 829045
802967 803424 802210 803516
762423 762157 761498 762809
713102 714604 713440 714358
658851 659292 659500 659300
598694 599959 595457 599807
542266 543569 542389 542985
488588 490368 489208 489070
442194 442501 443112 442797
404877 404960 405679 404631
374520 376563 375591 375195
354792 353640 355120 354837
334365 334336 333493 333941
325642 325616 324388 326326
321586 320363 320172 321665
333287 331669 330930 333795
339567 338202 339746 339671
333192 333664 332147 333056
323065 322572 322274 323256
295861 297417 296703 296874
259068 258690 257862 259308
212913 214364 213156 213236
166330 168457 167400 167137
120795 121250 121096 120935
75067 75584 75659 75344
30078 31595 31509 30312
4406 4646 4413 4231
2 5 5 5
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
