A = [
1062931 1393433 1663203 929310 1895876 1198659 1143589 1698709 1570064 1735256 1037577 1345259 1625203 1215407 1336515 1113206 1285689 1263937 1274420 1209649 1106823 1352137 1222261 1185912 1231081 1122371 1142847 1212153 1231803 1198091 1211464 1215867 1224735 1063712 1026923 1188803 1303749 1102796 1223028 1310117 1119035 1058862 1004359 1165933 1020533 1047110 1097144 1036691 1062860 986429 955753 1052436 1002084 1024022 984112 946457 1015594 905708 918792 887565 894594 939697 871624 905162 880855 845776 891647 842351 875825 828477 868247 878493 800855 823286 794283 835586 915172 861069 883725 891074 837246 823178 793950 802159 774277 778006 776860 723158 710805 704382 701984 703346 687591 684568 681480 672185 663629 653264 645584 633513 633280 630291 630666 627927 619524 616462 604268 594817 589888 581424 581071 571482 568615 565450 554687 557991 553275 549569 549477 542134 539001 532626 527408 522066 516557 514521 509561 501231 502120 495944 491980 487178 483275 481800 474806 472009 466045 462835 458591 454155 451675 449167 441135 440810 436216 434292 428496 424634 422372 418763 413188 409714 403110 398732 396794 394736 394191 387453 384259 381202 379710 373456 376260 369449 367203 365900 359165 356022 349649 347752 345139 344225 342893 343638 337373 334923 334386 328203 326714 321927 320191 317587 312578 308469 306977 304023 302413 298436 298420 293926 288568 288988 285407 285271 279764 276184 276624 268769 264982 261934 258245 257191 253860 253533 249994 247836 246394 241011 237919 234941 235262 234904 230191 228295 228739 222502 218390 216104 214023 210680 208773 205810 204928 203747 198721 197765 195799 193103 192308 190561 188281 186581 185146 183377 180755 178794 177756 175383 174438 172828 171167 169989 167953 165642 164809 163616 161529 160332 158313 157137 156471 156054 153667 151991 150945 150049 148907 146153 146189 144764 142717 142084 141380 140226 139329 137956 136514 134830 134111 131597 132138 129924 129895 128097 127056 125151 124860 123934 122840 121167 120331 118754 118136 117308 116370 115348 114462 112849 112095 111349 110552 109161 108981 107251 105774 105255 104468 103989 103311 100986 100902 100939 99257 98529 97697 97590 95713 95084 94289 93018 92492 92070 92016 91149 89343 88712 88149 87019 86765 86220 85860 84524 83318 83184 82311 82450 81013 80774 79315 79234 78186 77524 77474 75998 75649 75467 74973 73667 73437 72887 72559 71424 71873 70134 70399 69029 68882 68680 67917 67113 67144 66070 66089 65541 65742 64199 64349 63337 63203 62484 61783 61322 61327 60692 61214 59926 59335 59609 58545 58322 57800 57856 57615 56798 56119 56111 55402 55005 54314 54353 54493 53853 54104 53842 53181 52770 52542 52027 51282 51103 50640 50004 49535 49627 49585 48809 48284 47772 47281 47310 46775 46849 45999 45311 45499 44799 45116 43934 44215 44080 43984 42892 43148 43046 42749 42140 41720 41785 41450 40796 40837 40894 40388 39959 39708 40281 38936 39170 38426 38719 38527 38483 37835 37343 37672 37144 37399 37306 36229 36561 36195 35827 35957 35500 35136 34997 34058 35023 34002 34118 33673 33601 33356 33009 33245 32907 32601 32656 32308 32189 31872 31130 31626 31465 31270 30786 30534 30646 30551 30124 30538 29852 29633 29495 29832 29572 28983 29196 29150 28432 28976 28185 28595 27945 28190 27886 28520 27410 27314 27967 27493 27154 26821 26727 26829 26250 26133 26547 26208 25810 25792 25717 25719 25711 25353 25128 25858 25095 24913 24927 25367 25217 24254 24428 24367 23837 24216 23976 23762 23583 23586 23276 22953 23396 22961 22427 22680 22922 22525 22465 22034 21812 22049 21803 21720 21863 21789 21615 21238 21290 21193 21154 20545 20738 20524 20619 20345 20482 20372 20223 19939 19601 19926 19898 19863 19888 19428 19664 19384 19348 18811 18958 19028 19095 18918 19012 18639 18550 18777 18385 18162 18342 17826 18035 18086 17765 17898 17812 17660 17700 17431 17305 17361 17154 17575 16934 16666 17234 16830 16982 16866 16905 16919 16988 16683 16741 16477 16167 16051 15619 15857 15895 15978 15958 15943 15888 15683 15536 15277 16141 15305 15078 14655 15370 14793 14751 14917 14850 14517 14737 14217 14472 14429 14249 14294 13937 13994 13839 14039 13701 13679 13453 13567 13906 13567 13502 13218 13421 13307 13187 12831 13117 12725 13015 12885 12893 12764 12609 12824 12464 12527 12343 12034 12580 12322 12416 12455 12199 12381 13480 12123 11768 11886 11796 11763 11595 11365 11386 11354 11379 11565 11275 11103 10937 10957 11020 10996 10770 11066 10832 10777 10780 10801 10894 10455 10802 10659 10616 10542 10480 10529 10191 9953 10315 10138 10331 10267 9804 10034 10129 9824 9898 9610 9717 9972 9531 9903 9749 9323 9547 9348 9446 9306 9534 9405 9442 9105 8972 9313 9306 9153 8889 8952 8912 8966 8669 8910 8865 8629 8650 8417 8313 8309 8439 8701 8406 8519 8198 8488 8211 8019 8062 8238 7879 7875 8296 8033 7920 7871 7816 8117 7694 7820 7730 7790 7578 7729 7395 7555 7735 7348 7354 7301 7407 7616 7254 7164 7400 7136 7075 6988 6977 6967 6932 7086 6783 6683 6908 6848 6877 6657 6603 6857 6839 6629 6590 6453 6399 6589 6574 6584 6290 6242 6232 6424 6345 6191 6246 6235 6247 6248 6047 6358 6185 6056 6109 5712 6095 6004 5974 5853 5709 5701 5766 5693 5677 5697 5784 5783 6007 5476 5224 5725 5477 5557 5360 5468 5558 5456 5650 5272 5319 5238 5185 5483 5367 5192 5107 5277 5132 4880 4958 5016 5075 5049 4972 4938 4834 4898 4976 4814 4879 4711 4763 4693 4763 4723 4706 4541 4556 4628 4595 4594 4448 4551 4605 4620 4484 4466 4435 4428 4392 4372 4467 4344 4209 4174 4332 4091 4353 4246 4229 4102 4178 4081 4123 3999 3978 4006 4102 4076 4080 3901 3925 3897 4007 3863 3841 3940 3975 3782 3792 3730 3879 3768 3799 3683 3747 3745 3593 3815 3662 3633 3501 3592 3616 3464 3741 3529 3438 3414 3363 3469 3431 3308 3443 3303 3655 3286 3291 3331 3187 3309 3250 3276 3448 3249 3305 3287 3147 3230 3149 3160 3213 3101 3179 3051 2967 2873 3029 3132 2924 3011 3026 3068 2967 2856 2780 2930 2798 2981 2901 2892 2849 2888 2882 2761 2725 2904 2694 2703 2661 2797 2703 2697 2554 2720 2633 2678 2618 2576 2521 2653 2613 2701 2872 2470 2713 2594 2695 2481 2535 2576 2371 2429 2401 2489 2342 2480 2395 2406 2343 2449 2312 2381 2466 2221 2273 2220 2289 2337 2277 2185 2339 2197 2226 2086 2263 2234 2207 2155 2131 2200 2194 2118 2258 2086 2100 2056 2089 2087 2136 2070 2078 2069 2088 1941 1969 2006 2028 1921 1947 2060 2089 2126 2106 2161 2555 2176 2620 3039 3903 5462 20051 25316 22003 22896 19928 16817 19415 20341 17272 14281 19270 12534 7331 7390 8005 8465 6688 3858 2617 2686 2327 2271 2334 2109 2061 2103 2131 1970 1916 1913 1902 1873 1845 1834 1862 1820 1844 1833 1812 1745 1768 1769 1836 1749 1736 1748 1776 1776 1790 1744 1712 1756 1818 1723 1716 1788 1705 1750 1711 1657 1805 2356 1774 1734 1634 1733 1609 1549 1545 1550 1549 1443 1528 1501 1441 1411 1499 1487 1512 1384 1322 1410 1319 1241 1321 1316 1293 1247 1346 1339 1290 1244 1378 1326 1323 1295 1412 1517 1424 1390 1714 2272 3231 3419 3462 3202 2481 2096 2151 1908 1871 1813 1651 1636 1510 1484 1285 1278 1302 1474 1328 1468 1294 1312 1185 1240 1275 1247 1183 1129 1273 6417 1366 1245 1162 1150 1197 1223 1045 1098 1026 1047 992 1136 981 985 953 981 967 979 991 974 954 932 994 968 940 927 981 976 894 967 859 922 977 1032 887 948 900 903 937 939 852 911 889 863 875 933 853 917 896 921 890 889 903 894 837 893 935 1066 1026 1129 1009 1107 976 990 925 1011 890 1023 850 902 851 812 837 878 812 813 843 826 813 753 773 796 833 835 774 804 824 791 763 763 698 739 788 815 730 836 853 704 1046 961 984 927 925 877 863 876 842 880 856 843 787 797 883 827 793 824 766 901 785 746 728 771 832 791 1013 886 905 859 928 833 857 896 816 942 832 720 702 686 801 859 757 694 706 639 824 763 1005 778 1222 1784 1043 1313 1867 990 856 740 914 783 683 739 622 652 698 631 724 820 602 771 617 689 824 623 646 700 784 809 680 753 637 573 812 605 716 657 580 658 640 523 885 679 579 621 666 629 684 669 620 663 562 613 648 597 997 1457 1660 1495 1067 1823 1404 1626 1562 1415 1882 2069 1645 1727 1752 2459 2192 2364 1113 664 580 522 437 419 431 408 409 371 434 412 402 1018 523 517 421 430 440 445 419 403 405 409 394 403 367 410 428 415 379 376 347 303 333 377 326 356 344 335 323 354 316 324 327 368 330 325 328 297 307 342 341 302 288 287 308 326 290 292 313 272 337 267 331 303 278 279 266 286 278 321 277 282 254 286 229 280 289 294 331 312 277 274 303 272 278 287 265 318 245 273 249 245 282 293 263 259 252 257 229 242 237 285 254 257 225 229 213 260 285 235 278 233 255 251 223 260 232 244 213 201 233 262 219 238 230 227 224 244 213 250 196 249 208 236 236 237 226 234 200 244 216 190 243 227 227 205 207 216 202 205 229 209 199 203 215 169 234 174 196 214 189 185 194 184 205 191 167 203 175 212 212 205 205 209 181 188 171 214 196 196 195 203 191 215 185 187 181 195 160 178 192 186 190 182 189 165 166 165 179 196 175 191 204 156 168 193 167 176 176 162 153 205 172 140 163 157 162 168 154 162 172 157 147 161 154 163 152 171 160 174 144 150 149 153 154 148 156 142 161 140 114 188 138 113 142 127 135 156 140 121 113 151 136 136 144 143 119 122 111 111 125 135 121 112 127 117 90 81 143 111 124 133 120 131 92 108 108 101 106 101 94 114 110 96 119 101 106 99 102 107 89 98 107 101 101 113 102 107 84 104 99 92 109 87 110 110 93 104 78 74 96 91 88 80 108 84 111 79 73 80 82 79 82 83 98 94 105 89 83 56 81 108 68 93 89 76 73 66 75 88 69 79 82 90 66 80 83 75 59 80 69 98 73 85 84 68 91 67 75 74 72 80 60 68 66 64 72 71 90 78 73 70 75 84 77 60 63 77 73 79 54 62 49 75 72 70 65 72 69 66 59 66 77 49 58 57 61 68 59 61 61 50 67 65 69 50 69 70 61 49 63 51 49 56 51 46 56 55 52 66 56 64 61 47 54 71 45 62 50 56 54 48 58 55 48 64 43 51 46 59 47 55 43 52 45 57 54 47 34 42 55 59 46 48 49 43 43 67 58 67 51 64 51 43 42 63 34 59 42 44 56 46 44 44 39 71 45 42 46 47 47 37 45 52 42 49 40 50 50 61 37 49 45 47 38 58 32 44 41 56 44 46 37 45 36 38 35 40 51 45 35 34 41 41 46 33 31 44 34 43 42 32 40 42 46 27 35 31 25 31 42 36 32 43 28 41 41 54 24 28 43 31 36 44 35 32 36 38 30 34 29 32 29 47 28 39 40 31 27 42 26 33 25 49 27 28 42 27 42 30 25 46 23 33 29 22 24 30 30 31 29 32 29 35 28 34 28 29 34 33 23 29 33 
];
B = [
0 0 0
 247475 151461 96014
 451047 343271 107776
 306028 223380 82648
 254321 190083 64238
 222894 161571 61323
 211812 144564 67248
 174475 114260 60215
 151613 116893 34720
 152921 111551 41370
 324926 270726 54200
 196988 159193 37795
 218730 176635 42095
 195626 168374 27252
 203669 169430 34239
 290784 258300 32484
 230274 204606 25668
 236130 211549 24581
 228695 206849 21846
 250393 227506 22887
 276977 254982 21995
 248413 227378 21035
 256457 232588 23869
 261131 239434 21697
 257678 235872 21806
 308693 286565 22128
 276211 254668 21543
 298562 275821 22741
 278922 259824 19098
 293601 272782 20819
 317212 296008 21204
 322419 301326 21093
 321621 301053 20568
 305701 286268 19433
 392633 368900 23733
 332078 312466 19612
 327156 307234 19922
 731649 686576 45073
 335766 317066 18700
 387430 365250 22180
 649318 610708 38610
 400404 379194 21210
 587561 553762 33799
 350162 332506 17656
 402769 381523 21246
 610771 576225 34546
 406489 385913 20576
 599702 567095 32607
 406470 386385 20085
 582479 551603 30876
 414117 394107 20010
 568386 538068 30318
 420698 400291 20407
 581239 551643 29596
 420883 401497 19386
 602587 571065 31522
 572564 545249 27315
 409837 391551 18286
 543836 516269 27567
 350012 335236 14776
 68790261 67201688 1588573
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
46 9 2 2
0 25 0 0
1 54 0 2
3 47 0 1
3 59 3 1
9 193 4 5
27 233 31 28
325 366 75 82
61959 595 125 156
605143 938 242 247
1443261 1424 385 374
2596286 2047 809 777
3639685 3161 1757 1730
4749931 4387 4757 4835
6311891 6904 10823 11081
9878522 21867 23186 23583
10614165 32625 47825 48212
9124760 50642 69608 69910
6894041 80716 85641 85881
1980635 113079 112731 114437
200573 146311 134118 135742
191970 165452 158381 158730
186925 202232 176756 177190
194638 220237 194005 194350
193718 240215 202419 202890
193572 248047 204576 205576
187396 244315 200716 201258
180617 232281 191338 192396
168210 213005 177299 178948
155405 188555 162344 163657
143020 163051 146559 146798
131822 141118 132473 132209
121845 126506 120984 121306
116880 117229 115485 115729
114962 112327 112549 113225
114789 112098 112318 112310
116757 114346 114052 114932
122255 117697 119499 120299
129346 125701 126695 126851
136921 134127 135344 135842
147759 143421 144147 145147
159047 154936 155916 156936
171181 168120 169389 169501
183002 178869 180583 180482
193186 189738 190285 191538
202064 198590 199551 200125
205449 203929 204267 204885
207471 206497 206751 206851
205545 204224 204435 205351
200319 199325 199018 200327
189697 189819 189998 190599
176395 175469 175920 176899
159362 159606 159680 160334
142765 142669 142397 143052
123127 123906 123846 124779
106731 105993 105545 106156
90113 89892 90117 89913
75445 75018 75637 75062
63642 63352 63549 64133
54126 54478 55021 54960
47389 47115 47722 47583
42826 42875 42562 42776
39195 39203 39286 39286
36910 36527 36288 36485
34842 34795 34943 35238
34240 34217 34337 34299
33993 34178 34062 33914
34932 34557 34744 34689
35482 35159 35624 35451
36436 36451 36714 36207
38046 37848 38305 37634
39052 39463 40362 39439
38707 38470 38887 38709
36390 35782 35766 35502
31314 31162 31409 30862
26980 26201 26511 26072
21398 20315 21464 20036
15247 14537 15423 14445
12622 11464 12454 11484
9153 7873 9401 7851
6744 4744 6979 4609
3526 2116 3610 2180
83 106 102 80
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
