A = [
2120463 1965874 8571853 1983578 2012110 1906286 1878033 1890600 1885150 1841776 1888307 1985168 2072210 2200372 2406621 2534696 2658072 2823091 2849467 2838070 2866469 2821363 2781837 2771523 2788596 3331351 3355430 3393185 3893828 3449702 3487257 3457009 3046373 3103078 3058152 3058297 3042309 2981971 2974888 2940316 2933621 2923294 2943439 2942587 2938736 2960971 2916181 2898634 2879297 2823809 2809330 2802936 2792893 2787491 2776664 2766367 2752452 2734626 2715145 2699641 2679495 2664106 2644953 2636084 2620930 2608414 2593060 2577332 2565105 2542724 2521699 2503622 2480506 2466832 2451166 2432258 2414932 2392126 2369806 2348874 2337735 2309159 2290483 2269790 2251604 2235511 2221725 2197440 2175885 2159390 2136569 2120346 2097008 2078170 2064223 2047640 2028967 2010439 1992869 1976191 1954779 1935270 1915266 1900666 1881745 1866095 1849093 1830680 1815189 1796471 1778629 1758004 1747369 1726310 1709880 1694915 1680609 1664302 1652351 1632473 1615764 1601761 1579787 1569990 1547866 1531794 1518395 1499657 1487445 1471964 1457692 1442982 1425386 1409904 1394131 1378901 1365775 1350304 1337247 1323183 1307390 1291361 1280877 1266669 1252769 1239322 1224473 1212907 1196654 1184281 1172140 1159225 1144307 1136132 1117546 1105964 1095677 1079659 1066292 1054914 1043866 1033062 1019949 1008267 996293 981831 972778 960794 949106 940725 924991 915253 905942 896631 881681 870852 859023 850459 839277 827954 817863 806212 799269 790579 780473 770346 758725 748313 738917 727949 722435 715819 705100 695954 687406 679177 672622 663180 655487 646896 638389 628639 620145 613617 604388 596530 589923 580129 573862 567706 560948 550045 543940 533504 528509 522832 515666 508188 501223 495009 487658 480707 474827 466785 462428 455765 450392 444295 438855 431236 425496 420304 415319 409378 402226 397960 392326 385966 382471 375967 371064 365590 360762 356744 352172 347530 343465 338027 334367 328789 324755 320915 316633 312265 306955 303298 297142 294497 290187 285636 282693 277668 273560 271212 266834 263129 259484 255667 253446 249439 248240 243038 240794 237354 233622 228843 226458 225851 219987 218622 215677 211890 209351 205519 203721 200083 195432 194713 194359 189847 187605 184744 181672 178814 175360 173942 170819 168739 166532 165815 161794 158100 156493 155505 152807 149947 148126 146332 143804 140932 139823 138011 137138 135142 132823 130892 128276 125852 124337 122007 123537 119177 117043 115047 114329 112972 110585 108309 107282 105441 103614 102546 101262 100530 99415 96580 95551 94065 92526 91239 90788 89572 88847 87576 86820 85760 83661 82177 81370 80187 78366 78709 76637 74292 73113 72495 76578 70462 71295 68827 69499 67186 66768 65052 63984 62666 62458 62273 59923 59626 59769 58207 57667 57032 55690 55391 54931 54015 53928 52929 52204 51103 50534 49938 50987 49914 49059 48691 48358 47953 47089 46256 45931 45668 44647 43750 40581 40265 40250 39245 39053 38335 37613 37345 37182 36861 36033 35594 35456 34788 34415 33634 33614 33065 32922 32255 31889 31803 31376 30649 30613 30191 29596 29551 28812 28547 28313 27782 27920 27178 26777 26532 26060 25763 25523 25245 25175 25140 24404 23992 23152 23184 23274 22891 22258 22142 21881 21719 21740 21393 21187 21044 20614 20345 20318 20348 19613 19678 19565 19368 19075 18888 18903 18600 18346 18197 18117 18114 17568 17641 17150 16936 17244 16739 16490 16486 16030 16004 16297 16218 15863 15675 15493 15581 15367 15233 14983 15012 14503 14725 14402 14697 14495 14180 14200 13796 13830 14147 13520 13197 13478 13473 13212 13357 13006 13088 12942 12937 12670 12770 12739 12876 12609 12729 12530 12549 12176 12259 12276 11998 12074 11907 11959 11828 11673 11745 11491 11311 11198 11214 10956 10993 10815 10881 10887 10594 10587 10437 10428 10444 10177 10290 10141 10163 10019 10001 9848 9900 9993 9922 9837 9828 9920 9631 9699 9511 9619 9419 9531 9308 9104 9031 9049 8721 8797 8657 8555 8450 8691 8421 8576 8227 8353 8113 8042 8044 7871 8018 7910 7892 8041 7998 7772 7760 7735 7864 7656 7553 7529 7396 7589 7388 7326 7685 7414 7580 7443 7195 7393 7275 7173 7286 7459 7044 7033 7023 6857 6916 6922 6934 6765 6829 6733 6559 6550 6594 6472 6540 6417 6325 6253 6293 6375 6364 6356 6280 6176 6123 6184 5993 6032 6136 6094 5959 5957 5834 5812 6025 5754 5820 5750 5613 5753 5700 5506 5609 5649 5725 5734 5288 5400 5252 5294 5388 5445 5270 5383 5231 5159 5165 5018 5055 5175 5065 4910 5086 5666 5032 4862 4933 4811 4820 4811 4743 4956 4639 4857 4728 4717 4710 4693 4712 4623 4546 4461 4615 4444 4406 4443 4465 4346 4392 4466 4329 4371 4457 4282 4289 4287 4420 4302 4273 4215 4149 4182 4000 4169 4062 4061 4084 4179 4297 4210 4110 4253 4300 4391 4265 4335 4308 4202 4254 4125 4192 4252 4164 4176 4092 3992 4061 4083 4004 3958 4330 4076 4055 4065 4051 4005 4069 3988 3985 4071 3935 3853 3888 3676 3702 3532 3610 3753 3656 3519 3541 3600 3580 3408 3434 3423 3410 3406 3357 3279 3474 3271 3235 3205 3146 2984 3154 3142 3073 3087 3131 3041 3081 3125 2921 2837 2873 2931 2854 2780 2881 2786 2827 2884 2850 2741 2618 2663 2744 2776 2671 2777 2622 2657 2590 2608 2657 2502 2652 2686 2582 2554 2518 2447 2549 2496 2520 2595 2591 2590 2584 2643 2528 2630 2606 2631 2527 2562 2457 2637 2531 2543 2411 2447 2313 2373 2362 2312 2413 2391 2423 2348 3065 2452 2414 2424 2357 2368 2234 2394 2318 2326 2307 2361 2202 2142 2190 2224 2263 2240 2145 2118 2191 2062 2068 1891 1951 1996 1956 1905 1931 1947 1998 2014 1864 1945 1994 1847 1852 1926 1929 1974 1883 1867 1893 1969 1839 1932 1927 1920 1917 1844 1860 1883 1805 1937 1933 1810 1797 1800 1753 1884 1855 1930 1950 1758 1751 1895 1827 1792 1899 1787 1830 1924 1763 1727 1687 1796 1715 1794 1651 1631 1616 1630 1696 1672 1688 1658 1579 1523 1585 1559 1475 1450 1545 1347 1449 1429 1294 1352 1412 1364 1294 1282 1300 1228 1271 1295 1321 1281 1369 1353 1252 1299 1202 1284 1290 1243 1256 1277 1223 1278 1224 1283 1272 1230 1310 1231 1253 1187 1295 1296 1265 1301 1379 1351 1382 1219 1331 1263 1344 1199 1173 1112 1118 1214 1152 1191 1194 1108 1244 1152 1129 1098 1154 1086 1074 1056 1033 1041 978 1043 1032 1029 1022 971 991 977 987 989 1006 971 883 992 987 1015 1046 1012 1025 1032 1001 982 1038 986 968 999 1151 1059 1058 1041 1008 963 1085 1003 994 1028 1028 1077 988 1030 912 947 946 936 909 955 917 959 958 922 896 903 909 985 964 944 926 897 864 847 849 860 829 884 854 867 849 848 886 808 798 810 859 800 868 866 891 789 773 818 826 821 728 773 750 759 783 816 822 858 784 682 765 715 790 763 676 748 806 819 776 765 788 751 755 782 738 759 765 765 773 833 769 776 747 756 711 746 720 723 704 745 748 718 702 715 766 716 677 684 721 738 652 677 742 758 731 733 712 804 753 723 699 729 729 747 669 728 704 697 689 716 700 691 654 655 703 669 645 671 690 693 663 681 694 685 638 667 653 629 656 692 721 719 693 682 719 701 694 725 709 739 720 788 752 853 700 742 776 759 740 708 699 731 846 857 720 732 663 735 642 631 581 584 585 622 603 606 561 585 625 585 573 588 582 572 610 566 580 627 563 576 575 558 576 558 517 497 492 544 521 545 477 561 556 561 586 562 585 561 587 391 456 430 435 437 414 476 442 469 418 411 457 446 407 416 455 422 446 466 609 426 428 438 458 449 436 418 427 446 433 435 461 452 457 438 423 442 421 459 411 420 443 395 425 452 416 433 425 453 425 414 401 364 406 403 478 447 431 430 408 388 430 437 442 393 421 441 470 418 419 443 393 371 428 417 412 431 390 397 385 362 380 370 365 402 381 380 370 390 392 354 367 337 346 400 382 349 364 388 346 325 368 369 393 359 355 357 385 330 344 360 381 402 360 329 389 424 350 440 392 422 353 365 362 357 363 367 331 307 317 298 287 261 272 260 260 265 297 302 310 334 358 308 378 351 308 320 356 318 291 313 341 322 315 349 315 298 365 313 304 364 316 328 341 346 288 365 344 342 367 324 348 324 383 347 292 315 310 324 349 337 324 314 273 317 332 328 319 329 299 307 301 318 335 306 326 300 302 311 326 317 326 272 329 284 290 284 315 283 303 256 244 297 273 271 248 267 259 283 238 270 260 264 259 242 268 278 263 299 251 251 285 225 253 274 266 282 270 283 244 266 250 264 265 254 238 263 266 278 243 272 289 265 283 293 258 305 264 243 287 243 275 262 267 266 297 306 250 293 268 317 270 293 272 236 268 260 297 290 286 278 275 245 223 236 241 263 255 268 257 237 245 209 241 233 237 203 227 220 233 207 204 239 230 256 248 240 266 247 248 257 274 265 239 213 249 238 224 242 266 276 311 296 334 318 321 314 291 302 301 316 287 328 261 305 279 316 288 292 305 300 318 275 257 312 327 262 266 263 242 254 282 269 300 256 247 255 268 279 299 268 258 257 258 266 256 233 215 221 229 265 266 233 248 239 232 213 226 218 238 238 242 248 252 248 237 254 247 239 291 259 266 284 297 302 263 275 306 251 286 293 316 304 297 331 360 386 409 325 357 310 360 393 311 358 349 341 312 328 348 339 310 271 301 320 319 319 261 246 255 312 277 279 277 271 252 305 281 295 295 272 257 269 330 338 294 273 309 224 228 212 214 184 179 166 176 185 185 197 178 175 182 176 200 197 163 193 202 207 213 193 210 202 220 208 232 202 212 229 197 274 218 273 223 212 243 244 226 220 268 230 199 205 199 216 206 192 221 241 214 218 205 195 187 207 217 222 210 224 216 244 186 192 194 192 231 187 210 201 165 192 179 186 181 132 154 165 182 153 150 178 186 174 155 149 171 177 191 175 163 162 160 178 164 173 171 150 165 165 223 154 146 143 139 147 166 154 166 163 151 142 144 137 152 141 163 149 161 146 153 167 144 168 147 174 147 159 141 159 141 127 160 149 152 143 149 178 173 176 171 157 176 155 157 156 176 150 125 147 165 138 131 144 171 142 116 119 132 134 119 136 135 139 126 125 148 140 124 110 162 165 149 135 134 131 139 125 127 135 117 153 144 153 145 144 167 127 130 147 133 138 142 149 148 139 131 148 162 147 153 156 156 139 164 155 151 164 142 123 129 142 138 165 136 137 172 133 154 165 149 136 146 111 143 165 150 131 146 163 134 136 139 150 117 152 138 165 131 151 133 151 133 154 143 142 144 148 144 146 154 152 138 152 162 140 133 129 154 129 135 140 153 156 146 134 122 107 113 140 126 130 114 146 152 158 141 161 135 124 142 153 148 127 110 124 131 133 126 135 134 140 134 128 131 134 114 113 141 125 138 122 132 128 158 146 116 137 159 132 110 132 127 112 121 118 111 
];
B = [
0 0 0
 1490480 149978 1340502
 1514418 167368 1347050
 1615856 164990 1450866
 2388485 288214 2100271
 1422732 159551 1263181
 5433357 843029 4590328
 2217093 296408 1920685
 1370331 208973 1161358
 1338416 221883 1116533
 1004827 143503 861324
 728349 98644 629705
 496208 75193 421015
 393205 60913 332292
 801418 124382 677036
 717259 108272 608987
 655166 96198 558968
 1908647 332287 1576360
 1260058 191608 1068450
 1138247 185809 952438
 854997 141304 713693
 987158 185757 801401
 974993 192065 782928
 755472 147036 608436
 941247 188942 752305
 764119 150379 613740
 1415812 279747 1136065
 1178946 235940 943006
 949837 194581 755256
 1192438 255353 937085
 991676 215836 775840
 1244964 281957 963007
 1235778 289725 946053
 1178026 278706 899320
 1529631 362119 1167512
 1363793 330138 1033655
 1573188 384621 1188567
 2909727 607469 2302258
 1497819 375304 1122515
 1733692 433418 1300274
 2793104 603344 2189760
 1699716 432591 1267125
 2677173 597071 2080102
 1589058 409296 1179762
 1780202 466775 1313427
 2705332 617591 2087741
 1861419 490708 1370711
 2638762 613512 2025250
 1870354 509473 1360881
 2622283 635450 1986833
 1735891 481605 1254286
 2922930 719872 2203058
 1694166 483856 1210310
 2829065 710248 2118817
 1589462 457881 1131581
 2991019 775428 2215591
 2944179 785606 2158573
 1683572 509464 1174108
 2914584 782697 2131887
 1433605 454838 978767
 122764721 41507627 81257094
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
166 371 1 6
101 58 0 3
176 97 3 0
175 119 2 7
147 136 6 3
224 175 11 15
446 298 24 17
805 397 41 30
1559 497 133 66
4403 782 232 172
1292974 1087 372 266
2591022 1866 558 509
3904660 3160 878 759
5659607 6733 1457 1355
7354945 13883 2300 2066
9118327 29187 3635 3533
9686086 54605 5787 5570
8492773 87430 8557 8260
5681832 123093 11873 11892
2412781 157776 15456 15231
544865 188830 18775 18898
88809 214126 22193 22399
48528 222420 25364 24799
45056 201928 26924 27108
42466 163029 28226 28618
40897 123480 28361 29356
40832 90378 29638 29691
37178 68914 30129 30305
36456 55824 30853 30911
35136 48339 32529 31999
35067 43967 32889 33027
37900 43142 33641 34062
42469 44898 34240 34701
45185 45434 35777 36330
44897 44602 37195 38173
44903 44578 39279 39470
46269 45204 40449 41050
48530 47135 43045 43515
48136 47681 43774 44804
46776 46085 44610 44491
46362 46701 44487 44743
44059 43887 43297 43747
42152 42031 41107 41437
38695 38365 38254 37855
33812 33725 33814 33430
28263 28281 28128 27978
21767 21791 21749 21873
15485 15365 15697 15498
10368 10129 10186 10342
5885 5895 5791 5818
2820 2727 2683 2730
1051 987 961 996
295 275 314 270
32 52 42 42
2 5 2 6
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
