A = [
1616457 1503686 20741134 1077786 1057907 1010702 939097 1027294 851441 770427 777246 630192 618583 609227 601505 602229 595127 601266 602610 591673 587087 588962 583568 583493 602086 918835 925949 955709 1274000 1270695 1294881 1305254 1302782 1325833 1326726 1320690 1317724 1308060 1298197 1285206 1279767 1279942 1268534 1263369 1266776 1252519 1237914 1250269 1237472 1227235 1227235 1204170 1206661 1199685 1185421 1170886 1168430 1173771 1153474 1144214 1148152 1139459 1132408 1123535 1115331 1112850 1101215 1089344 1084278 1072173 1062932 1057099 1047220 1038231 1032574 1024305 1010247 1001210 986507 977997 967744 959794 946878 937567 931725 916805 905020 888556 874296 865947 856100 842732 837001 825967 817126 808413 799033 791514 782047 773646 765490 757902 746448 738109 731165 722126 713114 704474 698886 689760 680611 674286 668820 659980 651355 644440 635972 630187 620126 613576 606111 596537 591783 583164 576058 568364 562507 555818 547403 541455 534203 527017 520329 514682 507348 501597 495535 488054 482408 476799 471948 465363 458840 451807 447256 440799 436004 429190 425194 418511 411964 407622 402668 395833 390499 386398 380147 374814 370482 363997 360535 353978 349807 344873 340781 334594 330610 326343 322539 316987 311500 307967 303630 300477 296984 290949 285763 283294 279231 275966 271338 267255 263112 260147 255865 253325 247857 245924 242112 238667 235441 231562 227802 224382 221185 218962 215380 211736 208135 205593 203165 199195 196302 193906 190340 188317 185761 182700 179706 176716 174153 171310 168215 166262 164565 160787 158728 155959 153879 151643 150021 146635 145068 142528 140417 137864 135619 133588 131331 129535 126776 124797 123624 120972 119039 116556 114999 113598 111821 109699 108444 106233 105253 102941 101645 99722 98785 96387 95154 93189 91843 90804 89162 87434 86304 84692 83688 82163 81169 79909 77360 76670 75859 74343 73173 71637 70234 68790 68227 66820 65705 64657 63452 62686 61518 60179 59531 58184 57287 56217 55493 54649 54224 52855 51712 51120 50223 49160 48452 47338 46516 45543 45714 44081 43704 42947 41863 41377 40933 39653 39317 38746 37906 37329 36573 35730 35489 34775 34326 33730 33112 32377 31825 31126 30817 30074 29523 29302 28619 28201 27869 27383 26807 26394 25808 25416 24818 24335 24057 23766 23115 22975 22511 22034 21443 21048 20907 20441 19737 20081 19825 19230 18852 18468 18203 18019 17396 17220 16724 16374 16272 15970 15273 15315 15130 14753 14757 14296 14023 13893 13557 13403 13205 12718 12476 12424 12371 12090 11840 11473 11330 11185 11027 10828 10543 10425 10169 10015 9870 9630 9660 9357 9206 8723 8795 8680 8628 8443 8192 8075 7930 7688 7565 7665 7535 7150 7339 6947 6944 6707 6758 6477 6487 6388 6272 6066 6003 5797 5869 5725 5396 5463 5398 5143 5275 4997 4994 4923 4929 4832 4768 4695 4528 4444 4317 4278 4321 4238 4121 4011 3973 3776 3827 3691 3605 3582 3483 3408 3408 3313 3272 3192 3123 3148 3126 3060 2966 2916 2898 2798 2697 2682 2718 2572 2623 2497 2535 2402 2427 2369 2378 2308 2243 2200 2212 2137 2182 2117 2036 2021 1915 1938 1946 1947 1787 1915 1852 1866 1715 1748 1721 1673 1625 1711 1545 1556 1521 1500 1479 1471 1539 1414 1488 1393 1372 1335 1396 1368 1260 1318 1271 1230 1223 1187 1215 1162 1111 1114 1121 1146 1096 1074 1048 1044 1005 1008 1105 959 938 972 924 950 882 926 930 854 939 878 805 911 828 860 818 774 805 836 755 760 769 792 685 714 693 645 711 718 723 703 685 669 648 634 671 636 665 615 627 592 603 576 551 564 596 539 512 578 566 550 568 524 524 520 506 522 509 525 501 519 482 518 510 479 476 502 446 491 430 489 441 436 417 417 432 424 451 443 463 440 447 417 402 400 413 406 403 406 396 384 407 346 368 396 343 363 360 363 377 357 337 352 355 347 322 347 368 348 286 310 327 339 296 337 326 325 344 308 320 299 301 273 330 278 297 317 314 276 330 314 314 303 323 279 253 324 278 272 309 307 284 271 286 266 269 259 271 253 301 283 228 272 259 234 244 266 273 241 256 251 252 230 238 262 254 205 252 223 210 227 248 233 269 253 258 235 227 224 208 228 209 217 207 213 221 196 225 209 224 206 209 185 181 214 234 230 207 213 200 215 179 209 183 194 209 202 194 180 227 182 200 203 178 177 172 200 182 174 214 175 185 187 178 189 170 179 190 205 181 178 176 201 187 178 164 181 199 167 191 179 185 167 188 150 178 180 154 174 164 149 175 167 170 169 150 157 154 166 136 150 131 151 147 150 147 165 158 161 149 134 144 154 135 161 142 145 152 165 144 138 154 156 148 146 132 121 148 149 156 134 124 132 130 125 137 140 123 133 124 123 139 112 125 136 125 112 125 137 147 116 133 140 131 125 93 102 140 115 122 115 100 111 93 126 108 116 112 94 107 121 115 119 122 114 97 120 98 115 118 101 95 88 103 109 99 104 91 109 96 97 93 95 109 109 86 87 92 82 100 93 107 100 106 104 99 79 97 90 100 101 105 81 91 82 98 72 81 85 93 90 87 77 93 75 83 93 87 83 90 78 75 90 88 94 77 73 84 81 72 71 100 71 67 87 84 63 72 91 100 78 90 74 61 87 71 72 76 81 84 81 77 69 69 68 74 76 70 76 84 92 66 86 62 92 72 68 75 74 64 71 74 82 62 69 82 73 57 87 70 49 62 47 64 60 64 76 60 72 62 84 68 76 65 43 59 70 50 67 55 73 59 61 57 51 50 57 64 62 57 71 57 45 71 46 54 53 46 56 74 44 44 54 57 64 68 36 57 52 48 64 43 45 47 52 50 59 55 51 51 58 46 52 55 50 60 55 65 37 43 48 47 45 48 48 48 55 60 52 39 54 35 50 43 43 43 49 42 47 39 49 33 42 54 50 53 48 52 56 43 46 41 43 47 39 38 42 37 46 43 42 35 41 41 49 40 40 51 49 46 42 52 39 41 43 34 40 36 33 37 35 36 37 38 41 45 36 33 28 39 38 45 36 34 27 35 40 28 40 38 33 43 39 37 44 32 37 38 34 38 32 34 36 31 27 31 29 38 32 33 27 37 34 28 37 25 31 19 26 35 32 37 30 30 33 25 34 33 32 38 34 31 35 42 41 97 91 112 95 115 95 92 87 84 99 87 91 59 71 60 65 36 23 27 36 34 26 27 22 24 33 23 19 33 24 26 23 20 28 15 21 40 25 29 26 21 29 30 39 24 21 26 30 27 30 19 20 17 21 18 32 21 19 26 17 11 29 19 22 23 19 27 23 22 16 26 21 40 27 21 30 30 20 19 24 28 24 27 30 16 18 22 15 14 12 16 18 19 26 25 22 15 19 21 17 23 19 13 31 10 15 17 19 19 25 29 25 25 23 16 19 44 34 23 28 9 14 18 22 23 19 16 13 18 18 10 21 15 19 19 18 23 12 14 14 16 18 20 17 19 14 18 18 17 9 17 16 22 20 20 12 11 17 14 15 22 12 21 7 19 19 11 23 10 14 14 9 16 7 6 19 15 10 13 19 6 8 9 13 14 14 18 8 14 13 13 12 13 8 15 6 17 17 30 19 18 8 12 8 19 9 19 12 19 11 10 10 9 8 13 11 12 7 9 19 11 8 8 11 8 11 6 11 10 14 11 12 10 7 16 7 11 7 10 9 9 9 14 14 11 12 17 11 8 6 11 7 5 9 14 9 6 6 9 12 7 11 10 6 6 13 9 14 6 9 9 7 10 8 3 10 5 11 6 9 9 8 10 22 12 13 9 9 12 7 4 11 4 5 10 7 11 9 11 12 8 5 9 8 6 7 6 9 8 11 10 6 8 11 12 4 8 17 5 7 7 4 13 8 19 14 11 18 34 18 18 10 12 7 11 13 12 15 13 14 9 5 5 6 7 8 7 10 6 4 6 4 7 12 8 4 11 12 8 7 8 10 7 3 6 13 4 6 6 5 3 8 7 6 8 3 4 7 4 6 10 5 5 6 7 3 3 8 7 3 4 7 4 6 7 6 10 7 6 2 3 3 7 4 3 9 1 6 1 4 4 4 8 8 8 7 3 5 6 11 9 2 9 8 3 5 5 4 5 2 6 5 8 5 6 3 5 2 5 6 8 5 5 2 4 6 4 7 12 3 8 5 2 4 9 5 3 9 7 2 10 7 9 5 7 3 5 4 1 9 4 6 5 6 2 1 1 7 9 6 4 3 4 5 4 5 2 3 8 3 5 4 2 7 5 5 5 2 5 2 8 4 5 1 4 5 5 1 1 2 5 3 5 2 9 5 8 4 4 4 6 2 2 3 7 2 3 7 3 5 5 4 3 5 0 0 1 5 3 3 3 3 2 3 5 3 0 4 2 3 3 6 2 2 5 3 2 4 1 4 2 2 5 2 2 5 3 2 3 3 5 3 4 2 2 2 4 5 3 3 3 5 2 3 7 2 3 4 1 4 3 6 6 4 3 3 5 2 5 2 4 6 5 3 3 4 2 5 0 4 4 5 4 4 2 4 3 4 2 1 2 2 5 0 3 2 1 3 4 3 3 1 2 2 2 1 0 0 5 3 4 3 3 4 2 3 4 4 2 3 3 2 1 1 1 4 1 3 1 1 3 2 4 1 1 1 2 3 3 1 3 1 3 3 1 1 1 5 2 2 2 1 3 3 3 2 1 3 4 5 5 2 4 6 1 5 2 3 2 0 2 1 1 3 2 1 1 3 0 2 4 4 1 5 2 3 1 3 5 3 1 1 3 0 4 4 1 3 3 4 4 1 4 3 0 5 1 5 3 3 2 1 2 4 3 0 3 2 3 1 1 4 3 0 2 5 1 1 3 2 6 3 5 2 7 4 4 1 4 7 4 2 6 2 1 1 1 0 1 2 1 1 2 2 0 0 2 1 2 8 5 1 0 3 1 1 2 2 2 1 0 1 1 1 0 1 1 2 2 4 3 2 0 0 5 1 0 2 1 1 2 1 2 1 1 4 2 2 2 5 2 1 1 0 0 1 1 4 
];
B = [
0 0 0
 1047287 797600 249687
 529009 397360 131649
 1162408 915977 246431
 1023065 801185 221880
 558802 437497 121305
 1343089 1081131 261958
 696636 553156 143480
 1063995 863698 200297
 1239369 1002794 236575
 520864 419137 101727
 1761009 1436429 324580
 943759 772512 171247
 322960 263503 59457
 935717 779746 155971
 586199 485922 100277
 189065 155972 33093
 1007866 843112 164754
 357754 299416 58338
 91462 75763 15699
 51834 43412 8422
 28635 24165 4470
 22672 18957 3715
 1554119 1298608 255511
 565793 473306 92487
 161440 134702 26738
 1578744 1323145 255599
 652162 549204 102958
 153380 129728 23652
 2283434 1910730 372704
 817815 688630 129185
 264258 226600 37658
 1726001 1461912 264089
 809457 693613 115844
 2049796 1746531 303265
 702260 613565 88695
 1132187 979493 152694
 3543093 3060186 482907
 984436 862464 121972
 2060189 1799452 260737
 3565834 3085915 479919
 1261999 1107081 154918
 2376026 2077572 298454
 2841211 2459205 382006
 877585 770694 106891
 2621438 2301472 319966
 3253345 2829054 424291
 970670 846970 123700
 2892152 2561485 330667
 6262665 5493112 769553
 167087 145470 21617
 5541606 4933566 608040
 9378562 8292138 1086424
 510982 447764 63218
 4 4 0
 15180937 13519722 1661215
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
150 303 2 1
12 39 0 0
31 75 0 0
32 69 0 0
23 58 5 0
40 74 819 42
620 96 2297 194
9306 109 2778 481
49967 129 3497 681
188885 157 4736 1237
450267 192 5366 1866
1061132 341 6981 2602
2203456 516 8122 3769
4168377 971 9722 5406
6150320 1807 10951 7473
7439671 3086 13760 11111
6896386 4827 17217 15608
4919798 6821 22572 21927
2631567 10355 30085 29855
942669 14948 38667 39097
222914 22396 47780 48068
74869 31819 58049 58181
71185 45461 69095 69185
82111 61728 81500 81645
95860 80828 95256 95377
110190 101457 110666 111539
125899 123117 127720 127423
143122 142973 144934 146086
160831 163631 163283 163452
178276 182891 180665 180328
193665 199184 196175 196856
206845 213280 209623 209949
217219 225311 220873 221092
224456 233232 229263 228296
230036 237560 233076 233747
233032 239660 235207 235481
232244 239532 235480 235947
234397 238070 234440 235621
232710 237365 234172 234766
233823 236676 234828 234879
236381 238834 236439 238266
240571 243077 240900 242067
247938 249496 248534 249566
257081 258682 256881 258567
269277 270863 270005 270334
283146 284780 283942 284163
298492 298595 299642 297891
311035 313122 312395 312685
322441 324625 323646 324861
332003 332494 332244 331562
334579 335655 335247 334369
330941 333652 332773 333549
322254 324672 323993 325372
311269 312239 312410 311944
293371 294734 294186 295269
272940 273771 272074 273758
247677 248609 249369 248510
223913 225009 223967 223866
199241 200867 200146 199766
177829 178907 178924 178856
160539 161282 160747 160205
142503 142601 143602 143451
131028 130892 131369 131230
123590 124076 124216 124127
118946 119857 119093 118904
117173 117233 117352 117619
122094 122599 122113 122236
142173 141161 141467 141396
130025 130922 130913 130307
136791 136855 136834 137106
128854 129585 128335 128799
115211 114855 114504 115146
120885 121331 121491 121286
82078 82119 82493 82004
68150 68054 68679 68275
54899 55158 54318 55009
44732 44435 44585 44256
38219 37941 38193 37756
32022 32514 31709 31891
25006 25533 25582 25621
16265 16324 16137 16196
8052 8049 8170 8101
416 398 409 413
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
