A = [
1512639 2017152 2215679 1298374 2634096 1612127 1600882 2319719 2164894 2429234 1530362 1908122 2306528 1784938 1911461 1663426 1871135 1804095 1790600 1722270 1605510 1890152 1744497 1706607 1756635 1632941 1652299 1701942 1787008 1697859 1741452 1779501 1727749 1570302 1507816 1721483 1821692 1589952 1746253 1816411 1599506 1517018 1460522 1639545 1471034 1516494 1549143 1481925 1522656 1393411 1362085 1474770 1404657 1445782 1382574 1366879 1439499 1287353 1329920 1269925 1273981 1331903 1255087 1302283 1267498 1219974 1289085 1246469 1291342 1213305 1284833 1293014 1168139 1206345 1162819 1222086 1277062 1185434 1266586 1267635 1178352 1191358 1148116 1200230 1150869 1150061 1174613 1102078 1085538 1074347 1072404 1069546 1055288 1046672 1048734 1039978 1019245 1012485 1004042 986638 990331 980900 990001 986328 967078 970543 949502 939549 929639 920224 920153 905595 903758 900874 886143 893264 882594 881044 877128 862611 859155 847064 839979 835629 827826 827547 823547 810398 807875 799679 794627 790349 784460 780353 771836 762873 759103 752138 748393 742736 734848 732690 724395 718828 712186 709035 703198 697785 696955 688737 684146 674498 667617 661231 658934 656417 653035 645368 641704 638487 627806 622915 627125 619163 616943 614617 606200 602187 590780 587554 582690 583043 579152 576176 569420 566012 563739 555461 551524 546986 540223 538426 531903 526818 523244 516949 516459 511951 508634 504032 494749 497198 491455 488412 480513 475717 474694 467417 460288 454722 448869 448108 445498 442637 438418 435740 433049 425742 419496 416975 416102 414386 410530 405377 405141 396807 391884 388048 383041 379148 376749 372871 369697 364994 361337 359320 356111 353488 351943 347907 346965 344101 340371 337319 335579 331977 329389 328211 324781 323036 320381 318678 317820 313545 311809 309063 305614 304626 301786 299784 298082 295113 294251 289492 289102 287066 284815 282724 281640 278917 276896 274142 274411 270888 268916 267450 266559 263646 261978 259247 257624 256156 254602 251863 250414 247558 246927 244305 241962 241029 239172 238027 235065 233177 232453 231753 229023 225826 224825 223010 222542 220033 219213 218164 215590 215280 212516 211517 207660 207402 206438 204433 203283 202500 200214 198394 197213 196367 194391 192758 191766 189755 188240 187424 185028 184609 183405 182513 180046 179084 177625 175936 176509 174563 172465 171652 169735 169076 168435 166400 165970 164892 162491 162634 160779 160362 159239 156649 156584 155738 154571 153467 152954 149518 150549 148372 148983 146779 147345 144720 144036 143054 141987 141423 140763 140048 139318 136931 136564 137357 134497 134125 133395 133137 132605 130402 129395 129081 127358 127488 126441 126176 124365 123977 123204 122650 121531 120114 119429 118830 118453 117914 117143 116293 115418 114173 114279 112925 112835 111896 110234 109851 109833 107792 109262 107421 106933 106360 105543 104529 104354 103502 103083 101774 100375 100735 100039 99835 99728 97885 97590 96711 96170 96696 94935 95448 93036 94167 93717 92714 92152 92202 90002 91096 89356 89539 89012 87741 87065 87162 87604 86088 85322 85343 84371 84407 83237 83624 83207 81690 81612 81768 80886 80210 79255 79185 78785 78729 76887 77672 76697 76075 76502 75701 75080 74651 74451 74785 73639 72844 73486 72125 72141 71094 71541 70879 70316 70408 69503 69028 68472 68189 67295 67122 66721 67084 66269 66007 65046 65292 64881 64362 64523 63710 64039 62876 62767 62113 62321 62058 62084 60783 61217 60206 60350 59568 58950 59185 58756 58655 58266 57893 57722 57362 56695 56618 56652 56311 55725 55541 55328 55454 53808 53660 54437 53518 52966 52907 52503 52079 51781 51620 51313 51535 50495 50093 50065 50023 49308 49702 48642 49286 48675 48251 47884 47277 47339 47366 46836 46833 46342 45589 44766 45086 45443 45541 45103 44709 44026 44088 43447 43875 43292 43060 42978 42277 42751 42194 42155 42206 40957 41251 41292 41330 41481 40525 40914 40555 39730 39663 39100 39515 39679 38511 39167 38293 38515 38386 38106 37719 36981 37503 37406 36981 38029 36099 36651 36247 36177 35694 36131 35600 35635 34987 35450 34988 34866 34821 34821 33732 33914 33791 34176 33564 33774 33068 33751 33177 32612 32895 32303 32364 32045 32058 32272 31440 31917 31439 30868 31353 30617 30690 29978 30670 30589 29810 30932 29794 30071 29471 29231 28789 29191 29617 28473 28497 28653 28884 27965 28099 27327 28425 27691 27433 27158 27294 27212 26767 26452 26987 26748 26744 26613 25855 26681 25900 26198 25373 26174 25097 25742 25198 24893 25100 25116 24819 24649 24164 26633 24013 24851 23748 23940 23865 23606 24260 23301 23727 23758 23427 23095 23204 22575 22815 22394 22825 22576 22897 22140 22580 21759 22201 21633 21985 21280 21743 21546 21542 21441 21525 21038 20883 21008 20829 20651 20532 21075 21156 20519 20411 19591 20093 20246 19960 19833 20027 19561 19392 19578 19657 19259 18885 18757 18555 18785 18881 18769 18623 18278 17820 18208 17955 18001 17719 17760 17836 17922 17694 17237 17278 17109 17163 17352 17173 16961 17188 16750 18735 16845 16780 16649 17169 16396 16393 16538 17374 16784 16408 16075 16158 16077 16235 15734 15529 15629 15466 15371 15077 15447 15146 15477 15029 14820 14803 14615 14289 14713 14278 14858 14617 14289 14401 14279 14435 14637 14032 14159 13886 13639 15234 13800 14083 13584 13291 14039 13279 13910 14832 13249 13518 13174 12937 13438 12934 13902 13047 12580 12938 12426 12708 12312 12564 12474 12223 12391 12361 12079 12132 11936 12062 12265 12182 11704 11914 11611 11455 11644 11815 11570 11777 11304 12570 11401 11776 11258 11323 11121 11213 11303 11420 10995 10890 10876 10741 10886 10813 10702 10619 10643 10642 10370 10560 10229 10369 10355 10409 10193 10043 10107 9717 9889 10098 9956 10019 9787 9904 9999 9483 9599 9425 9783 9777 9293 11410 9215 9897 9223 9005 9167 9455 9163 10201 8975 9400 8827 8761 8837 8842 8766 8822 8945 8542 8501 8633 8432 8530 8470 8416 8698 8482 8410 8049 8132 8130 8044 8326 8063 7938 8067 7813 8477 7625 7717 7739 7689 10542 7696 7785 7568 7569 7984 7373 8101 9252 7364 7573 7464 7479 7159 7627 7691 6904 7054 6873 7230 7061 6940 6863 7359 6810 6865 6896 6763 6669 6581 6712 7416 6691 6824 6679 6554 6610 6479 6602 6594 6716 6353 7236 6413 6431 6364 6405 6207 6306 6303 7457 6250 6387 6210 6081 5801 6236 6295 5837 5836 5701 6056 5766 5713 5715 5706 5733 5643 5546 5866 5646 5707 5575 5714 5615 5419 5544 5414 5310 5523 5442 5615 5688 5204 5538 5271 5247 5485 5362 5153 5342 4940 6026 5177 5223 4862 5090 4855 5088 5085 4906 4842 4863 4906 4827 4705 4921 4562 4570 4763 4743 4657 4680 4590 4673 4533 4484 4436 4572 4727 4513 4549 4262 4455 4579 4503 4439 4397 4342 4325 4361 4201 4237 4291 4424 4161 4192 4272 4129 4301 4148 4039 4035 4140 4130 3917 4116 3954 3888 4022 3844 4019 3733 3747 3825 3816 3856 3844 3731 3893 3838 3879 3711 3681 3797 3637 3614 3695 3680 3729 3577 3463 3479 3430 3605 3698 3456 3430 3576 3545 3444 3316 3507 3528 3498 3507 3308 3562 3542 3481 3659 3425 3390 3571 3186 3338 3386 3087 3408 3217 3217 3275 3051 3196 3092 3323 3184 3139 3191 3078 3009 3100 2984 3114 3003 2920 3011 2888 2961 2972 2921 2825 2984 2901 2916 2794 2739 3051 2832 2712 2866 2899 2780 2650 2783 2732 2712 2688 2558 2701 2729 2786 2665 2575 2535 2548 2598 2562 2485 2578 2585 2598 2496 2461 2436 2500 2322 2426 2416 2435 2423 2348 2453 2379 2401 2245 2376 2247 2379 2307 2250 2328 2336 2226 2318 2121 2239 2235 2268 2279 2215 2345 2277 2255 2183 2118 2194 2136 2212 2193 2212 2096 2181 2129 2137 2144 2090 2054 2045 2113 2075 1985 2064 1954 2038 1907 2055 2017 1937 2004 1962 1995 2020 1803 1927 1952 1775 1955 1846 1953 2026 1877 1841 1819 1772 2016 1882 1909 1857 2018 1798 1777 1718 1808 1776 1795 1802 1789 1769 1774 1747 1669 1735 1771 1691 1748 1712 1720 1704 1701 1670 1709 1650 1807 1614 1701 1618 1618 1637 1602 1542 1605 1508 1674 1631 1586 1576 1373 1489 1555 1405 1581 1481 1476 1393 1521 1396 1426 1465 1489 1465 1347 1455 1427 1383 1313 1454 1423 1385 1355 1472 1330 1351 1353 1347 1298 1337 1302 1346 1323 1250 1272 1281 1353 1367 1301 1380 1232 1265 1310 1250 1361 1270 1292 1266 1256 1277 1136 1282 1183 1203 1293 1287 1250 1193 1144 1302 1158 1155 1134 1128 1104 1139 1143 1189 1115 1191 1112 1134 1060 1092 1056 1132 1073 1172 1138 1107 1120 1149 1090 1137 1062 1062 1074 1241 1116 1086 1049 1086 1062 1022 1038 1095 1071 1041 999 961 1072 973 915 1007 962 937 963 913 966 929 1013 1116 909 949 903 1001 1162 901 911 943 930 1067 967 971 868 892 928 929 901 952 862 920 834 892 891 852 927 863 779 865 830 905 880 896 807 844 850 795 841 801 824 830 848 938 837 827 824 735 916 713 841 894 747 854 714 779 722 732 728 708 801 701 693 714 763 729 720 738 688 645 756 764 710 725 615 712 668 757 631 707 647 695 666 720 660 713 645 636 720 642 611 626 657 690 703 645 596 597 598 615 627 636 662 634 634 587 629 577 632 612 643 555 560 523 596 619 607 616 590 611 531 566 559 604 555 602 536 563 588 579 562 541 617 583 478 507 671 520 577 527 507 625 515 541 580 498 570 520 491 519 523 565 564 452 533 507 515 483 455 524 479 516 482 451 494 474 546 482 496 475 428 587 448 464 474 459 518 470 453 479 401 459 436 443 444 426 481 434 387 413 420 488 435 473 450 481 442 413 396 450 484 507 426 471 390 532 490 447 381 384 486 440 404 479 438 398 449 372 465 410 411 491 359 376 389 359 606 327 410 362 363 384 401 371 437 355 390 458 367 357 384 347 323 316 358 390 335 332 344 363 306 323 349 414 328 348 328 307 308 312 294 318 304 309 291 303 304 299 337 306 333 266 301 332 278 296 291 291 305 339 268 271 257 349 313 275 271 316 304 294 272 312 265 294 252 272 255 306 296 245 269 249 261 322 264 263 300 285 373 290 351 267 353 259 287 251 384 287 300 277 272 258 244 229 258 236 210 287 232 266 225 273 230 256 223 243 240 229 223 228 227 204 216 212 205 191 204 211 189 211 192 217 218 206 184 193 210 186 181 181 203 216 212 179 183 193 183 222 204 197 202 218 196 194 208 192 189 192 204 213 170 187 179 195 182 210 215 205 184 154 192 170 161 184 185 200 185 154 167 158 158 174 196 189 188 155 176 191 171 188 183 165 185 181 182 169 130 175 194 155 171 135 145 180 178 146 170 159 151 165 144 181 160 156 154 156 141 153 178 151 153 171 141 138 146 164 155 171 146 146 139 136 135 173 162 156 148 142 147 145 143 159 138 141 130 160 175 138 153 138 150 175 119 134 137 132 162 148 142 121 150 151 155 135 127 147 132 126 164 163 129 121 137 160 150 140 131 123 133 141 139 144 142 129 146 143 143 181 157 149 150 141 166 105 178 129 160 124 122 164 114 138 185 113 189 101 128 136 138 127 113 109 129 145 135 102 110 132 132 125 127 140 138 125 101 127 128 151 127 125 93 108 174 128 114 113 102 154 113 116 133 107 138 105 122 119 120 118 121 129 126 80 101 114 112 124 96 106 103 99 109 100 127 91 111 117 108 80 116 97 104 86 126 98 100 117 108 127 93 148 114 97 116 91 85 114 110 119 
];
B = [
0 0 0
 526657 266896 259761
 644604 349577 295027
 390372 195086 195286
 1249804 741994 507810
 493868 274779 219089
 342063 182651 159412
 391262 220634 170628
 244064 128331 115733
 198582 100069 98513
 224672 125113 99559
 368715 234549 134166
 372734 241907 130827
 309557 196418 113139
 1230310 845730 384580
 471657 317839 153818
 550826 385234 165592
 357339 232312 125027
 539485 384064 155421
 555329 390795 164534
 389366 261629 127737
 1036240 747838 288402
 646063 458758 187305
 646928 462404 184524
 433014 294257 138757
 673532 480879 192653
 644518 462367 182151
 1005983 732829 273154
 441581 300683 140898
 746564 529725 216839
 746903 538534 208369
 465266 303495 161771
 796042 569118 226924
 741399 531802 209597
 1008923 714623 294300
 511226 340969 170257
 844270 600674 243596
 1281693 787407 494286
 782795 560658 222137
 642298 403057 239241
 1173158 751896 421262
 963684 678105 285579
 1169950 737331 432619
 547554 367369 180185
 887661 615694 271967
 1192933 756182 436751
 650354 421987 228367
 1210074 782426 427648
 921082 641554 279528
 1201548 780996 420552
 648030 425974 222056
 1178390 767453 410937
 945152 651450 293702
 1201800 782256 419544
 630457 405462 224995
 1292386 842363 450023
 1157933 758865 399068
 605241 389128 216113
 1179852 771957 407895
 748608 536799 211809
 99081025 71873297 27207728
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
7146 356 1 0
3 650 0 0
8 1980 0 0
14 2751 0 0
13 2566 2 0
93 10407 19 15
12801 8994 96 117
64208 15642 300 278
181856 24878 591 619
461533 36994 1157 1119
911623 57068 1652 1717
1856650 74877 2624 2606
3186174 109450 3489 3463
5343590 156902 4675 4844
7951064 221705 5975 5917
10848218 299521 7238 7659
12443051 376382 8591 8727
12072706 458081 10073 10249
9912560 548026 12160 11929
6551914 623743 14015 14109
3369919 681929 16766 16607
1275611 728619 20752 20300
330925 763302 24852 24653
68136 775252 28832 28563
32020 776553 32169 32477
31422 757961 34976 35155
33386 714396 37864 37919
34520 637719 39277 39489
36739 525353 40573 40305
37747 396676 41187 41457
40214 277007 42065 41745
41017 183650 43106 42921
43595 123377 45063 44730
47412 89988 47684 48240
52811 77855 53714 52962
59617 74222 59553 59466
66607 77829 66170 66029
73379 82741 74174 73866
82707 90787 83135 82694
91914 99046 91581 92187
102842 108886 102304 101829
112404 118962 112791 112440
124509 130730 125679 124812
131822 139211 131923 132184
138416 144653 138005 137905
142590 150149 143521 142575
142217 148903 142190 141811
137021 144182 138301 138222
129895 135989 131308 131304
119581 125060 120616 120555
104388 109596 106360 105949
89486 92715 90544 90215
73556 76201 73787 74147
58762 61024 59685 59832
45864 47318 47079 46345
35862 36751 36087 35960
27709 28477 28615 28683
22481 23045 22963 22903
18388 18669 19211 19349
16103 16197 16966 17122
14850 15167 15187 15038
14553 14709 14677 14860
14748 14703 14896 15155
15529 15453 15575 15689
16999 16853 17333 17142
18420 18779 18648 18394
20994 20556 20923 20891
28406 29060 25710 26130
27093 27174 27324 27626
31120 31275 31321 31070
36023 35825 36247 36023
40444 40361 41838 41838
44447 44575 44881 44643
48625 48842 49092 48863
51105 51181 51449 50775
53729 54017 53856 53530
53388 53754 53501 53479
50987 50777 51395 51391
48071 47765 47383 47718
37983 37925 38032 37924
24541 24595 24433 24479
11448 11397 11581 11522
600 562 628 597
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
