A = [
2939620 2807522 11210247 2756543 2712403 2570343 2513650 2537526 2512390 2449072 2449362 2476394 2491757 2494933 2523586 2535975 2551108 2594591 2575787 2565169 2587154 2570718 2565394 2590543 2711997 4483350 4509909 4619749 6381098 6214778 6410268 6456973 6273822 6393453 6490577 6447789 6292877 6294620 6242642 6156974 6104110 6087886 6043769 6011235 5995750 5922749 5852740 5790989 5701378 5633061 5570679 5524075 5484390 5437932 5388017 5367885 5271348 5206134 5142827 5074253 5008762 4949507 4894839 4840271 4792186 4740399 4685132 4630205 4575124 4512332 4450581 4393047 4339709 4286982 4234391 4184178 4137209 4078942 4021509 3971360 3915950 3854631 3811497 3763686 3709703 3665741 3614245 3568344 3516408 3464653 3417062 3365715 3315090 3272617 3238545 3196226 3146005 3099947 3057983 3014476 2963250 2926686 2881341 2847006 2804947 2768494 2737625 2697590 2650996 2615023 2573169 2527391 2488881 2453193 2414690 2383995 2349403 2312249 2295374 2244380 2207238 2169956 2135384 2097832 2057745 2028059 1995746 1966611 1935116 1908933 1889610 1855121 1823012 1794447 1767649 1734130 1784943 1680688 1656022 1628252 1600059 1572434 1550305 1527709 1502083 1477606 1455019 1428606 1401158 1380829 1361060 1336588 1311723 1297765 1267782 1246609 1227405 1205967 1182003 1164479 1146663 1126372 1101643 1086865 1068220 1046719 1030033 1009390 990054 974589 959067 942585 926422 911483 897269 879466 862262 848674 834264 819298 806821 789978 777735 765325 755702 741535 727387 714019 702079 687464 677378 666834 656561 646717 634687 621999 612000 602646 593573 582511 572033 561877 548749 538591 531539 521565 511845 502136 495149 487159 478368 466593 459577 449299 444161 436556 427807 419715 412540 408601 400863 392132 386232 379086 370541 362999 358965 355039 349185 340514 336621 330374 324753 318067 311264 306933 299722 295187 287779 282942 280163 276127 272024 266989 264460 259222 257062 250708 246938 243175 238067 234127 230473 226310 223314 217405 213140 211600 206560 204184 201672 195745 194126 192961 187430 184055 179275 175943 174320 172853 169962 166816 164152 162702 160485 156321 154418 149740 147969 149423 149360 142824 143017 139668 138603 136312 131975 130598 132227 128727 125725 123340 122531 121612 119103 116465 114389 112493 111700 113615 110517 107891 106616 106562 105413 100593 99679 102331 98406 96300 94641 94355 92347 91893 90258 88595 88160 85201 83539 81445 87469 76764 76390 74148 72457 75919 73030 69450 65406 64924 63565 62976 61671 61090 60588 59308 58927 57867 58351 57849 59555 59031 58248 58732 57482 56484 54503 53174 53767 52534 51990 52713 52550 50516 50312 49700 52262 47943 50435 47725 48603 47724 46185 45658 43143 44161 43447 42810 41434 41288 42259 39919 39457 40371 40156 39350 39442 38750 37962 37312 36381 36186 35637 34925 40920 38928 37869 38015 37930 38641 39098 38233 40362 37482 37778 35942 28588 28937 28669 28392 27934 28247 27308 27239 26837 27978 26301 26619 26371 26373 25656 25468 25098 25657 25475 25004 24684 24542 24047 23626 24137 23129 23102 22832 22604 22333 22545 22492 22663 22181 21309 20668 21429 21092 20470 20765 20428 19953 19640 19618 18240 18421 17934 17830 17821 17536 17666 17507 17237 17049 16971 17269 16835 16797 16566 16576 16198 15961 16077 15820 16035 15393 15193 15095 15252 14793 14952 14757 14645 14685 14611 14302 14486 14468 13875 13931 13737 13666 13665 13443 13487 13292 13273 13393 13307 13196 12948 13060 12968 12944 12796 12779 12894 12773 12714 12520 12689 12660 12391 12527 12281 12157 11897 12400 11989 12041 11948 12026 11678 11417 11401 11702 11349 11969 11908 11398 11075 10885 10790 10948 10787 11092 10326 10710 10873 11120 10632 10673 10779 10534 10769 10408 10613 10345 10367 10346 10036 10114 9859 10191 9804 9240 9580 10249 10093 9761 9765 10225 9928 10048 9896 9864 9524 9838 9841 9515 9606 9816 9848 9217 8533 8692 8627 8896 8378 8470 8550 8903 8769 8719 8968 8961 8341 8438 8655 7858 7955 7566 7715 7815 7954 7799 7539 7551 7339 7244 7149 7309 7350 7317 7631 7555 7618 7721 7172 6880 7124 6887 7033 6894 6881 6740 6607 6699 6684 6622 6797 6815 6638 6609 6748 6659 6859 6715 6214 6488 6546 6293 6358 6464 6279 6227 5957 5975 5921 6097 6015 6093 5876 5743 5991 6050 6138 5808 5650 5803 5823 5814 5594 5239 5625 5334 5500 5282 5241 5290 4754 5076 5187 4909 4966 4688 4718 4800 4963 4822 5080 4966 4872 4941 4648 4716 4779 4730 4840 4947 5598 5101 4873 4555 4266 4394 4293 4304 4164 4132 4189 4155 4053 4152 4018 4302 3936 3934 3956 3932 3877 3792 3765 4002 3918 3919 4072 4168 4098 4084 4123 4285 4289 4120 4144 4217 4097 3927 4338 3922 4080 4036 3949 4003 4134 4238 3882 4041 4081 3888 4007 4161 4196 4172 4215 4017 4095 4462 4626 4172 3985 4017 4473 4316 4414 4518 4297 4958 4253 4830 6105 5274 4567 4793 4369 4350 4244 4686 3979 3730 4852 4238 4470 4089 4349 4124 4425 4118 4205 4442 3413 3691 3689 3595 3184 3233 3069 3267 2928 3000 2930 3042 2940 2922 3231 3093 3021 2986 3049 2862 3071 2600 2578 2651 2610 2574 2537 2533 2721 2548 2694 2652 2541 2414 2501 2643 2451 2774 2635 2617 2604 2688 2621 2536 2628 2433 2368 2276 2215 2133 2217 2324 2326 2211 2163 2282 2216 2207 2238 2229 2345 2290 2312 2205 2415 2191 2290 2058 2068 2070 2086 2058 2073 2434 2255 2273 2270 2371 2313 2247 2336 2698 2715 2517 2493 2516 2563 2832 2558 2724 2574 2508 2330 2515 2593 2693 2745 2279 2362 2604 2249 2134 2050 2097 2116 1926 1939 1911 1832 1825 1755 1887 1878 2217 1961 1879 1941 2022 2042 1933 2137 1921 2397 2452 2448 2558 2451 2366 2478 2273 2180 2033 1977 2054 1611 1692 1624 1552 1636 1617 1989 1498 1737 1579 1461 1598 1534 1535 1638 1631 1732 1612 1689 1611 1519 1589 1516 1544 1471 1486 1543 1548 1579 1637 1409 1400 1342 1355 1310 1265 1314 1201 1202 1227 1195 1193 1187 1372 1251 1166 1183 1175 1175 1235 1069 1180 1152 1085 1118 1036 1059 1061 1101 1011 1039 889 986 991 973 944 1002 996 976 1044 1122 1036 1086 1101 1115 1067 1096 1104 990 970 1011 962 940 947 840 886 874 850 864 890 890 910 799 854 810 849 810 827 800 817 813 737 798 804 732 775 856 870 923 905 901 920 1146 893 856 858 752 766 752 748 668 691 738 741 727 713 758 693 687 748 753 747 748 739 706 784 780 710 1015 901 941 1114 1026 810 983 931 840 853 839 822 1001 840 1033 826 809 857 904 934 1041 1010 657 676 678 607 707 784 907 855 797 884 782 800 877 676 662 729 738 684 650 670 708 650 693 569 621 587 553 566 536 562 606 642 621 521 544 550 554 553 567 545 568 626 555 640 594 599 566 631 571 592 609 626 660 667 622 635 625 604 557 537 576 533 507 512 563 573 574 562 488 536 515 522 501 482 450 471 454 511 507 483 538 508 497 508 527 537 509 532 534 496 440 460 474 436 441 494 460 450 432 477 438 432 544 548 536 532 507 639 616 605 572 617 611 613 657 724 740 617 621 663 684 572 609 609 608 678 709 650 809 618 652 697 681 675 636 695 995 874 871 925 609 614 683 641 619 553 573 626 596 604 571 538 669 421 550 460 457 386 408 354 416 418 401 461 463 474 451 470 465 467 412 409 369 377 445 338 348 358 395 385 413 327 363 368 345 301 318 283 304 323 316 320 320 328 284 333 311 312 294 287 303 323 268 288 278 240 273 273 275 277 296 297 302 315 287 294 289 336 322 301 303 286 321 254 313 308 327 322 303 314 293 293 305 311 305 290 279 308 316 455 478 449 503 471 433 489 495 438 498 462 426 536 459 418 497 405 423 464 473 449 422 440 427 382 351 438 385 303 384 391 376 391 404 244 219 214 218 215 225 213 208 226 204 253 209 216 221 237 234 228 224 247 220 218 240 214 247 253 205 225 199 214 230 225 243 216 205 217 232 227 243 218 195 194 162 206 190 205 175 200 182 174 172 185 185 183 188 189 171 165 177 132 160 165 160 154 169 162 179 171 162 178 313 256 172 161 177 174 165 165 177 170 188 154 171 176 209 211 195 195 199 223 220 221 199 213 167 195 194 203 190 222 186 155 173 165 201 156 150 192 185 174 166 217 163 170 179 178 175 188 172 159 165 213 199 186 179 183 173 177 150 139 169 148 165 148 134 169 174 144 161 175 172 173 172 162 149 174 189 188 187 151 152 160 155 146 159 160 146 151 165 152 135 152 138 153 119 146 150 137 142 157 141 131 149 142 162 165 181 156 167 141 173 150 150 157 141 161 182 166 167 152 154 158 150 187 153 165 181 177 158 189 179 164 176 158 160 245 247 243 223 216 216 201 185 150 161 143 167 158 134 163 157 139 133 141 158 135 137 172 144 149 138 139 140 181 138 160 164 142 148 136 144 162 170 142 140 143 148 139 118 165 160 129 135 156 142 151 146 145 137 141 138 141 134 135 127 158 129 128 147 162 147 190 168 158 174 186 154 179 141 181 159 149 202 185 187 169 181 160 173 154 171 169 189 161 138 102 143 153 143 119 132 134 119 132 148 136 123 115 108 127 142 150 133 144 130 153 174 144 173 168 172 191 171 146 184 142 175 183 173 184 232 212 231 191 204 199 177 178 224 229 214 215 303 202 196 193 220 210 234 224 222 174 188 174 1021 836 1168 1677 1611 1112 1082 904 1294 648 106 105 94 97 96 105 97 121 102 133 125 107 120 138 124 115 125 121 116 125 119 94 105 125 121 108 114 129 172 139 109 107 136 129 115 132 110 129 150 105 105 137 122 100 121 129 121 92 125 130 99 101 132 118 103 103 103 111 109 88 112 132 94 114 100 127 109 112 107 92 122 97 97 98 80 93 79 85 83 95 75 90 99 108 116 122 123 99 99 93 92 108 107 97 97 91 96 100 70 87 81 100 85 91 100 89 117 98 75 103 94 81 90 95 98 102 94 90 113 96 99 89 108 115 87 114 97 98 96 115 94 99 80 80 98 103 92 83 81 72 86 89 93 86 81 87 102 89 91 81 73 81 95 67 88 85 88 110 87 99 98 86 83 94 81 92 89 98 96 94 107 83 85 95 81 92 90 94 80 90 76 99 86 92 87 101 87 87 86 94 79 105 107 100 84 82 82 112 101 86 84 97 78 90 85 90 88 68 87 94 80 98 117 95 88 111 96 88 93 80 78 95 86 85 84 100 134 127 145 150 162 71 83 90 90 83 74 91 90 88 94 105 78 95 88 77 80 95 55 91 76 85 82 79 69 79 64 47 83 59 79 77 97 93 83 77 73 66 53 71 56 48 66 71 88 77 91 83 76 100 92 89 95 102 97 97 96 94 91 91 102 96 89 78 73 76 67 76 66 94 101 66 81 80 84 74 92 72 68 79 85 93 67 75 
];
B = [
0 0 0
 1187763 55795 1131968
 644642 33575 611067
 2063158 116741 1946417
 636690 34029 602661
 678923 35603 643320
 922042 48773 873269
 1053738 62538 991200
 810887 46663 764224
 2029430 128803 1900627
 766321 59966 706355
 862165 69290 792875
 1075717 110486 965231
 1342781 90944 1251837
 654401 57705 596696
 1955041 126542 1828499
 691605 36791 654814
 731456 45946 685510
 767776 46604 721172
 1546838 85150 1461688
 823548 45109 778439
 2328159 146751 2181408
 1421298 74931 1346367
 1254873 71268 1183605
 2647919 129794 2518125
 3669886 202850 3467036
 597465 45179 552286
 10593018 643334 9949684
 336818 42622 294196
 707979 75400 632579
 457261 49211 408050
 715067 63901 651166
 314711 39510 275201
 2259536 184600 2074936
 260261 34911 225350
 562596 58968 503628
 368455 38923 329532
 626468 59168 567300
 160373 26296 134077
 2696422 220418 2476004
 70720 17711 53009
 133194 29139 104055
 156660 27389 129271
 582889 49550 533339
 263315 50609 212706
 125562 23131 102431
 175404 26752 148652
 318408 42921 275487
 4620848 369700 4251148
 135157 36392 98765
 155643 29357 126286
 139637 28433 111204
 210849 40118 170731
 365158 40227 324931
 5062301 428932 4633369
 222437 40014 182423
 163300 28176 135124
 214267 37975 176292
 2410332 192082 2218250
 2120737 200591 1920146
 245335921 31817366 213518555
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
154 331 13 2
74 57 5 1
76 81 1 5
45 114 3 5
44 152 9 4
77 171 135 25
2126 275 421 75
13525 304 601 252
66040 476 1097 526
212991 701 1760 1124
1570817 980 2436 1885
2323149 1893 3657 2910
2962643 3505 5323 4503
3603139 6975 7554 7071
3734284 12489 10420 9857
3454245 21942 14344 14020
2579982 32749 18512 18266
1532738 45033 22770 22807
690405 57037 27304 27249
216762 67358 31838 32025
71094 74495 35952 37062
55601 77597 41326 41909
58113 75155 47825 46606
61112 70205 53137 52837
64699 67069 58676 58938
70106 67307 64273 64808
75746 70834 70903 70898
80923 77035 77402 77839
89278 84380 86023 85792
95694 92695 93783 94514
104377 101365 102696 102987
113395 109835 111461 112016
123754 121474 121501 121258
134181 132120 132318 132372
145918 143947 143341 144274
156522 155632 155252 155667
169152 167204 166665 166619
179089 178596 178001 178170
187519 186927 186135 186979
192798 191507 191092 191589
194018 194074 192948 193160
189958 189637 188969 190872
180272 179378 179288 179639
163359 162707 163476 163372
142394 142838 142985 141934
117749 117963 117918 117978
90058 89972 90025 90113
63480 63906 63474 63659
41282 41459 40930 41438
22787 23219 23062 22970
10554 10469 10277 10430
3565 3602 3660 3578
1034 1018 1020 962
134 175 177 159
6 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 
];
