A = [
596822 596179 7222270 551324 537091 517825 512262 511250 511395 502516 540233 622429 686759 764458 890149 962539 1008666 1053195 1067854 1065480 1061931 1065173 1067195 1066863 1081903 1276151 1283655 1278620 1449025 1230986 1237470 1221214 1002945 1027804 1001519 998948 998045 965755 968226 960743 959448 959987 953055 957115 952791 947211 954545 951470 945548 952155 952925 951789 953503 949651 946460 942053 939083 932449 926986 922038 922080 920312 917231 914658 910965 908323 903716 935383 936534 934211 969495 970050 969723 968494 966224 958376 954551 950284 942508 936955 932626 929227 924374 923054 917988 913637 907961 900852 892807 888641 881594 877022 872213 866850 863052 858132 852007 846403 838084 831866 824999 818384 812679 808066 803981 796657 791371 784527 778895 771238 763136 756694 752700 743289 741819 734946 728872 722480 716788 708799 701827 697053 690562 683467 678014 673464 668454 661894 656781 648239 643578 635392 629811 624262 619424 613575 608103 603774 597786 591635 585106 579416 573740 567521 562644 555504 552411 545958 541529 535611 530201 524059 518235 512411 507659 502412 498217 493269 487839 483273 478871 472250 466847 461015 458032 450912 446913 442825 437000 432080 426065 423440 418568 412867 407823 403965 398208 393978 390074 386191 380750 376443 372993 367167 363162 358681 356763 350029 346960 343007 338790 335024 330439 327385 322436 319289 314865 311943 308580 303421 299853 296632 293217 290099 284740 281186 279448 274773 272423 268690 264490 262124 259396 255565 252187 248856 245790 242079 238624 234900 233250 231004 228198 225023 221416 218371 215517 213331 210303 208875 205067 202555 200367 197109 194222 192559 188656 187871 184470 181894 179534 177922 175280 171828 170308 167889 165390 163206 161887 159237 157052 154940 151506 150189 149162 146845 144911 142883 140805 138491 136248 135272 132439 131059 129635 127771 126149 124008 122397 121386 119315 117327 115726 114151 112730 111135 109259 107910 106423 105389 103878 101357 100444 99164 98341 96288 95214 93647 92117 91042 90225 88310 87327 86073 84859 83996 82438 81348 80524 79101 77779 77194 75480 75307 73773 72518 71566 70333 69451 68801 67423 66658 65617 64620 63657 63444 62196 61179 60416 59087 58598 57593 57094 56222 55472 54505 53514 53186 52424 51541 50619 49976 48930 48864 48006 47338 46932 45803 45628 44411 43899 43285 42896 41951 41471 40721 40313 39657 39342 38858 38405 37531 37044 36738 36093 35505 35146 34495 34277 33298 32878 32461 31911 31621 31506 30663 30586 30053 29460 29613 28834 28145 28223 27691 27254 27212 26093 26074 25631 25490 24904 24670 24682 24107 23706 23495 23036 22788 22467 22280 21737 21687 21193 20997 20880 20441 19996 19854 19472 19597 19282 18803 18640 18342 18143 17844 17703 17539 17088 17126 16729 16805 16335 16257 16052 15671 15594 15382 15255 15005 14865 14435 14420 14209 14278 13693 13594 13584 13646 13244 13105 12942 12748 12711 12513 12385 12082 11858 11857 11841 11739 11548 11329 11152 11130 11071 10795 10705 10544 10571 10490 10214 10135 10042 9842 9776 9621 9566 9557 9361 9312 9125 8948 9072 8750 8656 8667 8490 8487 8442 8483 8422 8085 8006 7891 7858 7774 7649 7618 7583 7385 7584 7306 7241 7286 7283 7003 6965 6879 7133 6724 6728 6724 6580 6535 6502 6399 6387 6149 6201 6070 6045 6061 5993 6062 5988 5757 5729 5831 5760 5597 5554 5535 5535 5517 5460 5403 5295 5295 5198 5202 5104 5039 5143 4903 4930 4908 4914 4954 4785 4809 4787 4750 4673 4662 4550 4664 4529 4380 4491 4422 4398 4314 4323 4239 4372 4293 4180 4231 4192 4054 4126 4048 4042 3958 3874 3887 3949 3863 3798 3851 3764 3841 3823 3656 3698 3653 3746 3621 3647 3541 3616 3617 3477 3446 3544 3438 3515 3455 3408 3428 3369 3233 3262 3311 3222 3370 3452 3342 3204 3124 3253 3113 3139 3097 3140 3093 2988 3007 3038 2980 3069 2911 2891 2938 2992 2854 2843 2933 2854 2800 2811 2841 2771 2763 2739 2756 2738 2671 2676 2736 2601 2692 2621 2636 2628 2577 2501 2582 2550 2533 2572 2443 2479 2426 2481 2505 2415 2435 2421 2343 2429 2381 2387 2371 2313 2339 2255 2230 2328 2272 2149 2264 2319 2188 2144 2139 2105 2155 2118 2034 2176 2060 2113 2041 2010 2079 2030 2060 2120 2069 2057 2103 2017 2023 2003 2001 1969 1893 1866 1997 1956 1837 1901 1860 1848 1880 1873 1834 1856 1872 1766 1840 1819 1766 1834 1844 1803 1729 1751 1727 1688 1767 1558 1668 1724 1721 1696 1642 1635 1613 1610 1678 1658 1613 1539 1631 1562 1552 1611 1630 1581 1545 1562 1546 1592 1532 1598 1476 1476 1598 1448 1498 1454 1452 1452 1499 1350 1444 1467 1499 1453 1471 1497 1379 1361 1358 1364 1373 1364 1347 1397 1370 1301 1349 1308 1330 1279 1296 1236 1289 1308 1257 1262 1232 1300 1289 1224 1229 1248 1241 1131 1147 1231 1186 1221 1184 1113 1164 1202 1167 1190 1152 1162 1193 1120 1129 1156 1086 1113 1150 1101 1110 1152 1114 1151 1067 1092 1146 1065 1045 1089 1076 1036 1027 1057 1049 1021 1030 1014 1012 1003 994 1017 1019 989 983 974 1002 1003 991 949 968 926 954 995 935 947 953 949 959 892 921 963 927 856 958 885 916 875 905 909 904 902 891 833 854 919 866 862 859 859 838 821 844 851 813 856 830 873 826 826 793 809 802 793 802 740 748 800 806 753 789 771 828 769 758 750 757 709 748 755 747 749 760 706 717 730 761 787 741 718 700 710 729 723 701 743 708 653 715 678 654 700 668 687 658 658 710 649 631 669 661 662 638 643 665 647 611 634 629 591 589 576 611 587 611 571 568 628 587 607 559 627 603 581 582 564 573 575 558 601 574 559 517 554 576 553 537 546 522 540 518 530 518 538 511 519 521 531 552 519 540 523 489 523 459 483 509 475 508 501 476 479 448 474 456 463 473 465 451 444 457 487 498 469 461 448 441 451 456 444 456 430 450 480 438 432 468 462 424 457 439 426 411 400 439 439 435 429 439 420 400 392 415 432 437 386 401 380 427 390 384 373 402 396 383 384 383 350 408 380 380 407 381 370 378 396 371 375 363 376 350 360 360 366 352 365 362 366 347 365 328 344 340 324 324 320 363 327 344 344 351 337 323 325 335 319 297 325 343 324 308 331 290 316 300 318 303 286 285 285 267 298 304 290 305 283 280 264 275 306 305 270 266 279 274 289 266 258 293 293 264 289 265 282 285 258 272 244 259 253 241 271 279 284 258 242 251 246 257 254 248 231 234 246 242 250 217 224 249 256 259 220 211 208 230 214 233 250 214 245 240 256 233 238 197 193 220 229 202 220 213 199 225 220 219 236 192 213 214 212 208 196 221 204 199 204 209 207 197 222 195 189 203 185 190 181 191 190 182 173 188 174 194 171 174 189 171 174 190 162 200 187 170 174 163 176 162 169 167 142 157 157 182 160 174 171 142 187 164 166 180 165 163 158 160 163 158 155 160 161 165 155 143 161 154 140 131 149 128 165 160 156 135 152 167 158 136 150 162 142 153 135 148 133 155 155 130 138 116 132 136 165 134 125 134 137 136 118 131 112 154 127 130 135 151 134 120 127 145 116 130 127 134 114 133 131 115 97 120 114 121 123 132 117 138 101 108 92 105 124 131 123 117 116 125 111 106 120 105 102 94 117 111 108 118 115 112 105 114 87 97 117 118 103 103 111 107 105 113 110 95 94 116 87 81 111 91 99 98 100 102 99 97 93 79 97 120 81 85 104 76 97 98 79 83 86 99 107 95 91 101 87 90 88 79 73 92 110 55 102 84 96 86 94 88 91 91 83 80 97 84 87 72 93 75 94 84 88 77 71 81 82 84 70 68 86 71 81 67 77 80 74 96 69 79 63 61 78 80 87 83 85 77 79 78 71 79 76 64 63 72 64 67 67 64 68 75 67 66 68 80 66 50 60 60 58 52 72 79 74 67 76 67 50 49 56 48 54 66 58 59 56 52 64 66 72 58 45 58 67 57 51 51 45 49 60 51 50 64 55 48 53 52 45 57 45 48 62 44 59 48 64 59 42 51 40 48 53 48 54 53 36 47 42 58 54 50 56 46 48 42 47 47 51 49 55 48 45 56 47 48 55 46 51 47 47 48 54 49 45 58 49 50 39 49 52 43 58 37 50 38 52 50 41 59 37 42 46 41 40 36 46 38 48 44 50 46 36 51 39 38 45 48 42 47 37 57 34 43 44 37 44 34 33 30 40 37 25 44 45 38 33 40 37 40 43 45 40 37 50 34 34 34 33 40 30 25 36 29 39 33 32 38 36 31 41 37 42 48 32 35 28 36 37 34 29 24 30 35 31 35 33 28 39 24 31 31 34 27 26 45 30 21 32 19 36 45 24 29 36 31 36 27 35 38 35 18 29 25 26 17 27 39 25 28 30 36 18 24 35 19 25 22 17 27 25 27 19 24 27 28 28 19 26 19 16 19 29 20 22 33 30 30 28 22 24 24 23 26 30 26 21 21 29 24 15 21 28 31 16 29 15 33 16 17 17 25 25 33 25 19 19 29 16 22 24 17 25 22 16 12 23 15 19 19 22 17 20 18 15 19 18 14 20 19 12 15 22 15 18 26 15 23 18 23 13 12 20 13 13 16 14 11 15 17 20 18 16 15 15 13 9 20 20 18 14 15 19 18 13 12 12 19 21 15 19 21 14 18 11 22 11 15 19 12 15 21 12 13 19 20 14 15 12 15 12 9 17 10 14 11 9 21 18 14 12 12 12 11 12 12 9 16 12 15 12 11 16 11 11 12 14 13 8 10 15 10 16 14 14 7 9 11 8 5 12 11 14 8 10 13 7 14 15 15 20 4 8 3 12 6 6 14 10 10 7 14 6 10 11 18 8 10 12 8 11 12 9 4 13 12 17 9 8 8 11 8 8 10 11 7 4 9 7 3 15 7 8 8 7 13 13 10 10 10 5 5 3 6 4 10 5 9 8 7 10 7 8 8 9 2 7 2 8 5 12 11 10 15 10 8 9 6 8 11 11 8 11 4 10 6 7 12 3 9 3 9 5 3 9 6 7 5 10 7 5 7 7 2 7 9 7 6 3 13 4 8 4 6 7 5 6 7 8 10 4 7 7 9 7 6 7 7 5 6 8 6 6 7 8 4 8 10 7 4 6 4 5 8 6 5 7 4 10 9 3 3 2 8 4 4 8 7 8 3 7 7 6 8 2 5 6 5 4 5 6 7 4 
];
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
 426086 348718 77368
 345598 281606 63992
 445234 365227 80007
 431256 353473 77783
 557486 457288 100198
 387976 317339 70637
 479130 392891 86239
 957708 781228 176480
 456352 374862 81490
 486388 398190 88198
 871958 712917 159041
 562843 463459 99384
 834334 683260 151074
 427703 351846 75857
 551817 454750 97067
 860918 705632 155286
 511576 420904 90672
 844674 693344 151330
 574116 473534 100582
 844964 694344 150620
 517990 427733 90257
 832357 685265 147092
 615532 508326 107206
 843927 695149 148778
 524211 432986 91225
 898578 740629 157949
 838802 692905 145897
 525603 435243 90360
 847270 700137 147133
 504670 421580 83090
 71949204 61605143 10344061
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
4 40 0 0
2 5 0 0
0 12 0 0
5 12 0 0
4 12 0 0
5 14 1 0
153 21 0 0
1604 25 1 2
23979 37 26 5
125696 42 79 28
296603 56 690 126
655784 86 987 280
1281639 129 1197 518
2247228 260 1745 967
3222475 635 2431 1681
3997405 1375 4006 3479
3974834 2409 6640 6441
3208781 4137 10986 10779
2023828 6660 16578 16839
879778 10251 23927 24044
259738 15981 31326 31676
79330 23299 39260 39418
58228 33927 48337 48409
63850 46390 57971 58266
73960 60728 69295 69182
85833 77025 82202 82565
101059 93463 96271 96701
115477 110571 112616 112232
132668 127149 128747 127765
148374 145098 146170 145454
164519 160420 161875 162008
181180 176299 176548 177302
198041 190459 191021 192667
205071 202267 202926 204119
214737 214173 214213 214184
225459 224163 224008 224242
233607 234979 233724 234228
242721 243384 242232 243471
251924 251878 252579 253280
262893 262611 262963 262823
274045 274129 272826 274277
285960 285970 286905 286578
301482 301129 300331 299919
316097 315937 315112 317080
332779 333128 333877 332379
350416 349802 350813 351625
367134 367375 366487 366356
380373 380358 379997 381263
390334 390630 391058 391227
394433 394870 395522 396237
394254 395673 394362 394787
386490 387079 386365 387216
371053 373524 371203 372239
351483 353621 352261 352481
326008 328148 326763 326702
297465 299709 298842 300348
268119 270151 268672 270134
239788 242435 240714 241761
214175 216273 215081 215507
192995 195334 194294 194106
177888 178548 179124 178646
167689 169145 168451 168324
162126 162316 162609 163204
159466 158845 159485 159266
162542 162794 162679 162941
171342 172775 171459 172207
185507 185242 184781 185377
201536 201826 201742 202295
225592 226272 226121 225920
248739 248964 248690 249877
277273 275883 275701 276470
288779 287826 288570 288366
303130 302408 302558 303392
316052 316343 315204 316843
314525 312964 313421 314638
292818 293068 293151 293663
257393 258346 257144 259794
193759 194820 194177 194802
105918 105554 105437 106170
38637 39257 38871 38519
6095 6078 5930 6091
40 33 21 42
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
