A = [
2146127 2970777 38328595 1598625 1714100 1653542 1598171 1686227 1615908 1583021 1571263 1520496 1541238 1509407 1489372 1498242 1450905 1455747 1457348 1419012 1402918 1400581 1389461 1388573 1375736 1381219 1388238 1371391 1374813 1358016 1358886 1365616 1345339 1333941 1334486 1344823 1328873 1316582 1321436 1327556 1314459 1324198 1332605 1328202 1338729 1339094 1318480 1327147 1321750 1307578 1304093 1277602 1286717 1284826 1263545 1270093 1261508 1267527 1254028 1236317 1236455 1225648 1213495 1198337 1189961 1182324 1165262 1153686 1144074 1131068 1125589 1127082 1121390 1115875 1115818 1112566 1105219 1099639 1084448 1072343 1066409 1059878 1047712 1037813 1032422 1021903 996345 960904 947515 936419 929964 921140 918172 910164 902781 897678 890964 884928 881059 871686 868122 862420 857669 852002 845140 841299 835786 828278 824403 821367 813265 811762 806855 799899 795318 790769 787797 781946 775805 772236 766679 759510 753805 749007 741651 735566 731097 724879 719487 712715 707528 702420 695153 691812 686383 681127 673700 670097 664473 658311 652775 647040 642763 633963 628434 623871 617931 612659 606003 601782 594842 588606 583004 576447 572019 565413 559570 554123 549818 544969 538674 532804 528376 522301 516295 510331 507002 502034 495911 490513 485076 480640 478040 472760 470158 462893 458852 454027 448434 443336 438971 434745 429461 424945 420726 417313 411876 408732 404872 399882 395176 391909 386683 382203 377524 373981 370940 366136 362416 359168 355806 350476 346851 344772 339178 337440 333023 328112 325352 319955 316737 313039 309070 305156 302682 299596 296037 292647 289673 285439 282843 279952 276963 272853 267187 263081 259151 254974 250145 245184 242186 239747 235492 232105 229706 225766 222970 221222 217019 213670 211400 207544 205838 203030 200342 197538 194691 192187 189774 188216 184498 183165 179486 177759 174712 172454 170612 168461 165350 163301 161261 158177 157136 154516 151970 150355 148167 146736 144282 142318 140411 138826 136376 135126 133190 130492 128921 128329 125151 123962 121926 120189 119156 116857 115595 113861 112024 110885 108372 107343 106177 104365 102722 101876 100090 98583 97321 95050 94047 92840 92336 90082 88831 87513 85897 84934 83413 82383 81539 80233 78865 77349 76967 75276 73907 73251 72415 70792 69648 68953 67876 66916 66039 64678 63752 63204 61817 61216 59593 58943 58319 57278 56472 55380 54611 53685 53087 52259 51538 50730 49394 49124 47945 47336 46491 45873 45171 44626 44074 43059 41868 42302 41272 40612 39926 39320 38559 38330 37522 36974 36214 35894 35304 34759 34583 33124 33125 32584 32007 31634 30732 30168 30158 29756 29252 28642 28109 27816 27814 27097 26347 26301 25790 25459 24743 24263 23699 23443 23277 22875 22587 22108 22015 21536 20934 20463 20470 20010 20148 19537 19283 18993 18698 18741 18330 17794 17608 17299 17188 16456 16221 15929 15760 15637 15438 15005 15017 14547 14232 14187 14098 13727 13436 13293 13262 12881 13072 12219 12337 12186 11927 11732 11658 11609 11417 10918 10898 10864 10667 10374 10362 10165 10090 9712 9912 9613 9582 9421 9232 9170 8997 8826 8792 8663 8322 8269 8208 7887 7826 8055 7826 7654 7490 7376 7269 7176 7155 6907 6913 6796 6736 6769 6504 6280 6414 6285 6167 6166 5995 5908 5755 5697 5520 5572 5347 5458 5315 5137 5085 5149 5023 4919 4829 4771 4806 4751 4780 4562 4532 4477 4608 4419 4303 4336 4108 4199 4187 4031 3983 3966 3933 3753 3756 3683 3643 3613 3483 3495 3432 3521 3409 3270 3401 3251 3290 3178 3190 3127 3118 3250 3047 2942 3014 2856 2860 2820 2809 2818 2657 2661 2745 2663 2675 2614 2664 2542 2554 2524 2576 2435 2547 2447 2442 2361 2428 2382 2270 2237 2339 2323 2246 2247 2262 2082 2077 2092 2117 2061 2013 2125 2080 2000 1948 2046 1857 1964 1945 1848 1788 1794 1886 1805 1838 1765 1754 1765 1734 1730 1663 1671 1693 1773 1650 1653 1713 1795 1648 1634 1669 1585 1658 1570 1602 1532 1626 1535 1478 1614 1463 1510 1524 1568 1552 1489 1386 1456 1455 1423 1437 1396 1408 1427 1456 1359 1299 1358 1382 1336 1333 1314 1285 1303 1318 1270 1265 1321 1246 1312 1265 1123 1218 1242 1217 1177 1237 1221 1171 1225 1246 1135 1205 1111 1117 1151 1185 1135 1140 1148 1157 1210 1147 1158 1145 1285 1116 1170 1186 1207 1100 1113 1749 1152 1095 1094 1079 1096 1062 1040 1093 1106 1056 1092 1009 1073 1011 968 1021 1054 964 984 955 968 996 992 929 906 913 931 925 914 897 865 949 920 981 936 898 932 904 889 898 873 877 905 868 870 868 878 845 874 836 836 869 871 825 816 843 824 877 864 848 840 864 878 860 808 857 797 792 869 728 858 828 817 794 834 743 752 772 702 739 727 731 736 701 724 707 696 717 645 701 634 667 653 723 721 631 662 712 620 683 701 707 685 715 700 728 679 681 727 638 722 714 721 710 758 733 652 740 744 663 752 725 733 671 672 652 697 677 665 633 644 684 655 660 679 660 662 699 775 675 715 627 701 701 686 686 663 726 601 639 654 664 693 601 643 603 661 618 673 643 608 680 571 606 607 613 583 625 637 545 561 542 538 596 592 598 599 577 579 526 562 477 486 541 544 519 527 546 533 550 485 526 518 540 522 550 560 520 573 533 501 517 533 525 489 528 541 501 527 474 493 499 520 503 538 533 562 558 540 496 554 585 554 503 550 560 541 511 515 547 569 558 485 544 540 572 513 504 487 489 576 533 486 495 476 456 469 413 436 430 434 409 426 440 448 423 441 450 430 442 433 485 452 438 403 386 435 403 438 392 427 408 409 408 400 415 407 388 412 368 435 423 388 412 406 419 363 397 366 388 360 421 386 384 383 437 424 407 424 405 459 442 497 440 456 438 497 495 429 432 442 425 431 409 399 438 450 469 434 430 393 407 380 389 407 397 422 407 390 384 379 417 381 368 395 401 406 384 402 404 373 363 379 348 403 358 390 340 352 345 343 314 312 321 353 330 370 375 396 375 361 392 369 377 383 404 379 408 447 404 404 351 326 320 293 347 379 737 313 340 364 350 351 365 357 353 357 378 372 339 334 344 350 362 325 297 285 322 297 340 300 310 336 351 342 364 355 388 347 362 414 331 372 344 319 303 329 335 295 304 290 310 282 300 280 344 284 294 307 279 303 279 299 282 277 339 339 331 304 270 277 294 326 299 300 316 279 298 272 294 335 338 342 366 396 425 523 646 691 742 811 773 801 843 788 773 779 888 642 615 582 656 612 564 660 598 630 581 652 613 669 615 658 721 791 749 917 703 611 635 797 731 690 608 598 576 571 542 577 620 590 576 623 598 530 542 470 460 495 421 340 275 376 551 250 260 231 237 646 259 265 245 249 280 266 297 263 248 267 308 295 297 309 288 314 336 337 318 339 347 361 381 357 379 349 337 396 412 432 405 431 463 370 431 450 478 507 469 554 566 682 720 690 779 765 895 901 896 918 848 877 849 808 855 909 904 928 981 962 760 630 508 443 374 308 308 267 215 154 198 209 179 188 178 180 220 187 208 199 229 241 214 218 215 211 215 217 258 268 228 223 213 241 248 237 257 213 262 237 208 217 258 228 248 249 235 214 210 221 186 218 165 194 181 181 189 192 201 204 197 180 204 195 213 195 158 199 189 192 200 181 192 209 203 191 175 174 222 180 185 191 187 189 174 217 205 242 185 188 186 197 186 211 201 213 227 188 183 202 170 181 167 167 168 168 137 140 155 176 178 179 183 181 157 168 151 168 175 164 158 162 162 134 188 147 141 262 157 188 188 157 156 142 162 134 158 139 147 177 161 191 189 139 171 169 182 168 164 178 182 188 222 196 185 226 185 196 207 186 198 175 194 347 282 188 183 189 242 250 220 222 245 275 262 265 271 259 271 252 254 303 258 272 266 269 236 168 178 179 153 229 225 206 203 220 208 194 207 247 216 225 255 239 264 246 246 258 236 204 246 228 226 227 237 231 220 259 251 239 240 227 210 243 210 230 197 230 241 218 190 209 199 282 262 270 231 260 241 266 264 212 198 165 182 164 134 161 156 148 139 149 174 180 154 153 193 157 166 176 175 197 176 198 134 139 153 141 149 146 145 159 125 137 172 163 152 158 155 179 156 137 158 136 144 172 165 184 148 164 163 193 163 168 164 177 181 160 169 197 147 165 142 157 143 162 143 170 206 214 187 215 263 292 300 301 248 281 239 196 192 198 175 183 178 164 149 135 168 145 124 142 146 139 125 141 145 152 148 145 146 126 168 149 134 133 127 140 151 112 129 106 115 111 110 111 135 129 149 130 116 132 142 101 113 113 89 110 115 99 120 136 120 129 128 110 114 102 112 92 99 69 77 83 72 84 79 80 90 100 69 83 97 94 88 117 104 103 82 96 98 102 110 93 89 97 107 99 84 97 96 88 111 98 128 95 104 109 115 125 113 121 118 125 147 110 141 127 109 106 122 121 116 134 108 111 126 110 133 101 124 129 128 140 108 127 124 129 123 121 123 100 107 110 111 96 107 98 119 79 79 98 97 111 98 102 102 99 101 93 102 87 77 87 106 107 96 94 80 79 94 83 81 83 89 78 68 63 84 94 79 97 93 87 98 84 77 111 71 93 90 88 90 70 94 76 76 79 93 82 103 99 100 85 86 94 91 72 80 106 93 98 91 76 102 87 77 78 85 78 92 97 97 78 84 71 82 95 77 103 104 78 83 109 86 87 74 78 98 115 106 98 89 88 74 83 85 86 107 94 86 84 83 81 84 114 58 79 86 101 79 74 80 87 82 81 101 100 71 87 129 112 108 80 96 80 87 77 101 99 70 98 111 95 100 85 112 117 107 115 138 122 95 100 111 108 103 100 96 90 85 130 100 95 87 90 96 55 98 62 64 68 55 57 50 80 81 95 94 100 88 97 97 83 88 96 132 108 116 104 121 127 85 94 86 76 97 98 67 63 55 65 58 56 51 51 61 64 63 74 63 57 52 71 53 56 52 61 45 65 48 75 77 60 80 72 84 64 72 76 72 95 71 73 63 95 64 78 79 68 96 62 55 53 73 80 92 78 83 87 96 96 78 88 111 113 136 89 105 96 120 100 72 96 63 83 91 63 59 76 67 64 57 56 52 51 50 46 54 59 41 41 41 49 55 68 42 57 48 53 55 50 53 35 56 61 49 66 53 64 
];
B = [
0 0 0
 800072 517851 282221
 923247 666800 256447
 811923 584221 227702
 1305001 1059770 245231
 552409 401992 150417
 2152449 1904104 248345
 804907 679664 125243
 314444 237356 77088
 693576 612330 81246
 237741 185596 52145
 128953 94331 34622
 100150 74725 25425
 131883 107088 24795
 909491 848015 61476
 877907 818236 59671
 477955 428570 49385
 2567425 2436095 131330
 633094 577834 55260
 1110964 1043861 67103
 424709 386405 38304
 1177934 1114290 63644
 1144800 1085720 59080
 419871 387149 32722
 1130266 1074712 55554
 426442 395650 30792
 1946702 1863249 83453
 1186778 1131740 55038
 407138 380084 27054
 1192279 1139242 53037
 402977 377729 25248
 1193121 1142636 50485
 1147218 1099092 48126
 421994 398576 23418
 1455758 1397740 58018
 453566 430218 23348
 1155646 1109043 46603
 426138 397873 28265
 1138959 1095815 43144
 1134574 1091530 43044
 469047 442949 26098
 1095038 1054795 40243
 449621 426171 23450
 1181732 1140988 40744
 1061919 1024986 36933
 418178 397155 21023
 1081900 1045442 36458
 449490 428586 20904
 1058221 1023811 34410
 444020 424588 19432
 987290 955908 31382
 1082603 1047362 35241
 369297 354768 14529
 1012292 979539 32753
 364180 351195 12985
 1012991 980330 32661
 903902 874918 28984
 457907 443878 14029
 964861 935133 29728
 362348 351917 10431
 85131178 84016072 1115106
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
193 184 3 3
115 28 1 0
147 102 0 0
153 68 2 0
94 70 3 1
106 93 6 3
2381 174 38 9
14727 152 115 37
68828 190 568 107
286390 273 918 250
899036 325 1075 383
2590621 418 1418 638
6090357 550 1752 873
12228663 794 2064 1243
18838342 1111 2384 1640
24290131 1352 2573 2095
24697559 1692 2904 2611
19953244 2275 3150 3176
11670720 2898 3813 3863
4304172 3522 4577 4775
836767 4464 5326 5481
71420 5667 6115 6342
11493 6623 6833 7251
10671 8394 7595 7854
11059 9134 8510 8341
12486 10718 9177 8998
13354 12141 9888 9970
14569 14429 10985 11202
15560 15403 11651 12306
16406 15024 12478 13075
16344 15597 12873 13245
18245 17280 13243 13618
16957 17093 13510 14071
16711 17364 13031 13403
16658 18400 12859 13134
15915 17671 12948 13394
16002 21380 12781 14151
14436 14170 12320 12343
15308 15846 12646 12682
13645 13703 12845 13026
15134 14395 13320 13800
13969 13931 13020 13119
16811 16355 13337 13573
13887 14295 13944 13852
17946 17370 14363 14251
16553 16487 15032 14783
15666 15551 16886 16491
15091 15292 15177 15074
19563 20337 15536 15518
14718 14544 15097 15289
13647 13749 15071 15438
13646 13308 13752 13675
11905 12196 13192 13321
10616 10477 11948 11864
9162 9006 10020 10049
8239 8283 8560 8559
7832 7658 7543 7900
6677 6689 8045 8317
5711 5840 7167 6610
5618 5506 8079 8405
4985 5089 5458 5484
5540 5510 6270 6014
6579 6864 6559 6587
5000 5011 5798 5655
4931 4921 6550 6673
5321 5210 5051 5034
5362 5274 5651 5705
5724 5826 6293 6482
6567 6542 7048 6985
6806 7008 7312 7267
8197 8281 8184 8379
8264 8418 10794 11015
9182 9167 9269 9200
9542 9481 9609 9403
9230 9283 13901 13757
9738 9684 8776 8585
7881 7766 7726 7750
6912 7177 6460 6536
5809 5826 5885 5822
4825 4647 4745 4695
2935 2856 2879 2878
1838 1885 2057 1994
89 88 115 96
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
