A = [
1154155 1576647 1642545 988939 2010496 1207084 1224991 1749891 1476397 1777341 1237740 1291023 1672279 1359230 1376601 1242836 1377796 1344047 1319269 1309467 1223585 1380173 1308221 1272211 1325970 1217198 1223022 1254950 1333980 1268459 1247347 1326531 1266043 1173952 1148451 1240897 1353604 1198476 1284723 1346700 1169890 1143444 1096553 1195069 1115451 1128942 1158486 1103322 1140823 1060889 1044445 1113276 1063953 1093923 1060286 1032186 1073224 994582 1006925 987436 984707 1008135 980136 994630 971204 954395 976931 945899 969357 932085 963639 960605 910234 927693 899724 931798 976631 949777 953652 952822 932144 913381 894616 905490 879493 886674 875725 839576 832003 826207 824919 825701 809712 810792 808657 802928 791353 781070 772109 762904 760739 756521 758923 753287 742429 751508 738307 733125 728707 716962 724266 709942 706193 706666 695442 698292 693186 690056 693635 680849 679930 674988 673824 667228 660805 656722 653571 654777 647286 641392 636858 629847 631799 625300 622846 620593 611952 610142 605722 607163 604839 596391 593393 586407 586439 582935 576816 575544 571902 569719 565387 557583 557624 553198 552608 551803 546880 540981 539547 534257 526562 528102 526394 521727 519479 518339 517033 512263 506855 505116 500107 500610 496895 495637 492271 487277 488443 481987 480700 476294 474349 475204 467912 465479 463961 460443 457120 452586 449172 449118 437778 437861 433020 431672 428728 423248 421769 415492 410569 406098 401093 402000 396385 399150 393554 389559 388964 379340 377340 374934 374135 372966 369445 363948 364980 357080 352760 350293 346848 344501 343543 337041 334486 337887 327309 325409 323163 320633 321797 316618 314571 312111 310796 307601 305818 302831 302600 299567 297422 296892 293132 290795 289732 285813 284552 284054 280924 279688 277118 275618 274863 271735 271451 270666 265868 264785 263404 261839 262432 257606 255990 254503 253223 252828 250717 248458 249160 245458 244481 242850 242483 239467 240436 236699 236776 232822 233717 231116 229538 229486 226904 224431 224506 221961 222070 220694 217759 217615 215302 217067 217006 211573 211689 210118 206402 207569 209553 205650 208489 201449 201635 202030 199132 198460 196726 198602 193972 191971 191591 189714 189677 190003 190374 190228 183601 182487 183509 180552 180729 180384 179642 179382 175920 176650 173243 173455 172175 171510 169291 168816 168596 167860 167477 165226 163899 163915 161301 160461 159339 158568 158284 157415 157398 153585 155589 154026 153070 151812 151602 149950 148612 147878 148358 146553 146971 145161 144911 144545 143322 142871 141695 140552 140561 139375 138616 137878 136382 139449 134179 135303 134766 134183 135288 131786 132325 134861 130206 129045 129091 127922 136680 125985 129858 125977 123828 124169 123370 124068 121723 121913 123334 120342 120572 117697 118456 117264 117679 117165 115730 114503 113939 114140 112048 112119 112545 111147 111036 110511 109094 111661 108726 108747 107391 106807 106703 105205 105568 104205 106385 104274 103792 102506 101669 101655 100521 102439 100039 102098 99875 104946 99528 97349 96933 96706 96553 100557 96688 102959 93345 94388 93994 92385 93332 92496 91302 91965 90051 93013 88915 91103 89582 88210 87998 87351 87969 85994 86102 87446 85732 85259 84259 83521 85737 84142 83111 84061 81989 82089 81375 80927 83612 82587 79903 79065 80263 79560 79195 78254 80631 78219 78557 76401 78683 76628 75159 76686 75652 74506 74234 77060 76640 72649 72649 77003 72142 71792 72342 72456 71431 71874 70179 69626 69199 69868 69574 70146 71258 68248 67449 66950 66851 66968 67364 65457 69115 65002 66777 65206 64730 63796 65532 62874 64592 62019 62768 61317 61682 65139 60813 61020 60178 59818 60885 58878 58984 58919 59164 59125 58399 57720 57594 57777 55956 56422 55866 56392 55356 57436 56555 57839 54015 54329 54630 54996 55415 57332 53038 57969 52659 52114 52295 51150 52598 50780 51005 51962 51013 51220 50602 49842 50108 48752 49068 49731 48444 48462 48257 48262 48008 48608 49220 47199 48102 46731 47866 46658 47333 48067 49659 45789 45415 46155 44753 46249 45122 45133 48933 44234 43424 44295 43990 44413 45932 45237 42879 44185 45490 41634 41681 51825 41841 44049 41032 42729 41708 41914 40422 44929 40740 40536 39157 39907 39298 39920 39810 38408 38570 38048 38031 37614 37842 37247 37282 40140 36754 37604 36081 36245 37148 36287 35624 36344 35605 36283 35376 35178 35064 36421 36597 34354 33957 34470 33776 34250 35553 34237 34809 32814 33187 32602 33467 32031 32538 32119 32447 31926 32139 31301 31053 31183 32713 31080 30984 30835 30372 30428 30565 30172 30568 29819 29932 29852 29382 29337 28627 29171 29217 29987 28697 29439 29000 28761 29753 29662 29140 30064 27972 28542 28693 30315 27723 26670 27560 27405 28344 27149 30702 26628 25933 27498 26551 26556 26720 27499 26289 26005 25595 24888 27444 26158 28167 25070 24756 26058 26185 24646 26242 24355 24663 23729 23569 23720 23298 23579 25101 23367 23499 22936 23316 23427 22494 22788 23252 22098 22077 24172 23122 22783 21925 22045 24327 21706 22081 22186 21406 22090 21827 20574 21642 22368 21254 21020 20414 21743 22761 19967 20314 20489 20646 20220 19843 19715 20100 20217 20748 19218 18973 19242 19878 19232 19464 18698 18932 20850 18804 18385 18454 18145 18297 18919 18694 17984 17894 17516 18258 18807 17718 17274 17285 19330 18088 17591 18438 17315 18002 17813 16557 17202 16620 16494 17085 16072 16609 16106 16727 16289 16209 17248 15620 18548 15471 15660 15806 15376 15488 15411 15046 16575 15152 15896 15624 15266 15076 14919 17101 14210 14520 14890 14170 14426 13724 13756 13937 13958 14181 13972 13537 13318 13483 13646 13300 13334 13145 13323 12902 12930 13115 13327 13131 12720 12683 12709 12714 12531 12540 12501 12533 12104 12323 12084 12275 12044 12238 11914 11922 11916 11574 11803 12156 11800 11484 11563 11388 11747 11377 11261 11388 11277 11275 11239 11116 11209 10969 10979 10789 10813 10820 10762 10724 10735 10581 10791 10403 10594 10385 10657 10272 10368 10670 10136 10702 9929 9844 9795 9738 10114 9823 10448 10101 9657 9626 9525 9673 9330 9347 9650 9507 10868 9387 9326 9263 8871 9808 9160 9183 9024 8736 9604 9546 8745 8586 8596 8685 8523 8724 8596 8498 8259 8394 8358 8357 8278 8386 8199 8669 7937 7978 8036 8047 8015 8852 8066 7965 7938 7875 7828 7808 7807 8925 7680 7475 7671 7668 7486 7587 7474 7637 7634 7432 7525 7166 7348 7737 7212 7551 8855 7222 7186 6922 7498 7765 6914 7083 6907 7140 7079 6720 6748 7489 6984 6752 6670 6551 6722 6483 7354 6381 6521 6448 6512 6225 6423 6572 8010 6406 6340 6104 6529 6038 6098 6395 5961 6207 6348 5888 6074 5913 5969 5954 5819 5676 6061 5817 6224 5930 5817 5808 5621 5490 5745 5483 5503 5729 5589 6569 5491 5534 5352 5418 6349 5396 5585 5299 5212 7406 5139 5287 5145 5151 6166 5109 5346 4888 5101 5315 5109 5216 5249 4934 5218 4780 5165 5020 4764 5038 5715 4961 4897 4826 4704 4820 4542 4945 4759 4691 4574 4440 4702 4622 4591 4606 4378 4597 4570 4508 4581 4279 4431 4250 4472 4283 4393 4328 4355 4362 4350 4336 4334 4132 4045 4280 4463 3979 4183 4182 4319 3998 3974 4575 4198 3800 4208 4162 4131 3850 4353 3813 3787 3630 3942 4269 4208 3549 3699 3648 3668 3459 3509 3550 3641 4060 3463 4733 3507 3511 3619 3458 3452 3313 3780 3407 3424 3264 3200 3372 3429 3393 3244 3225 3506 3318 3250 3366 3160 3293 3217 3183 3175 3167 3130 3201 3040 3054 3258 3382 3018 2998 2935 3221 3290 2842 3134 2971 2895 3065 3093 2984 2898 2906 3324 3105 3313 3008 2817 3089 2827 4202 2854 2676 2651 2700 2600 3358 2715 2869 2575 2668 2775 2939 2614 2635 2591 2672 2484 2640 2538 2542 2415 3594 2428 2606 2509 2516 2529 3738 2432 2573 2440 2438 2515 2943 2347 2694 2459 2929 2887 2531 2647 2362 2344 2404 2439 2563 2386 5003 2314 2249 2264 2362 2198 3546 2209 2587 2154 2210 2439 2138 2320 3037 2177 2535 2111 2346 2204 2080 2104 2131 2138 2250 2083 2105 2040 2174 2065 1916 2024 2005 2040 1963 1978 2105 1917 1864 1998 2065 1913 2014 1848 1975 1843 1957 1888 1897 1884 1833 1821 1788 2351 1844 1859 2142 1762 2772 1840 1711 1862 1709 2323 1971 2126 1846 1731 1740 2215 1664 1780 2661 1952 3547 1771 1877 1691 1749 2482 4066 1786 1721 1816 1782 2142 1725 3633 1714 2586 1501 1644 1855 2483 2217 1569 1451 3854 2697 1788 1970 1413 2351 2248 1524 2624 3526 1339 3005 1504 2316 3859 1384 2656 2333 2384 3508 1509 3374 2458 1713 4262 2131 3205 2064 1725 2130 2522 1493 3860 1914 1274 1340 1785 1745 1638 1670 1554 1423 1169 1217 1206 1239 1172 1151 1208 1171 1124 1185 1156 1181 1171 1083 1168 1178 1163 1098 1123 1156 1141 1086 1128 1046 1053 1069 1094 1076 1082 1037 1060 1040 1044 1096 1054 1092 1011 1007 983 1034 1006 1038 1006 1050 1038 996 1023 1078 990 1030 1038 968 1009 983 932 897 933 942 1008 956 938 969 941 951 938 866 887 934 900 947 869 853 868 917 990 865 880 894 835 878 843 837 900 803 910 832 883 832 834 765 744 836 753 883 859 795 853 750 768 729 804 727 837 813 781 863 756 813 813 836 779 817 776 765 780 762 756 790 769 816 705 743 702 686 746 787 708 660 698 702 691 743 743 745 714 665 720 700 656 669 618 663 709 677 685 702 610 695 668 667 668 673 623 750 639 667 636 600 636 632 618 645 573 620 601 566 529 571 547 588 541 551 542 588 548 532 635 570 554 501 608 580 525 597 535 564 573 503 597 506 575 496 469 526 508 479 554 481 499 535 482 502 513 492 492 489 484 499 507 551 487 466 511 444 515 446 481 473 480 488 438 536 443 450 488 485 459 469 455 446 475 472 446 443 446 443 436 423 442 457 395 429 497 409 402 422 438 385 384 424 460 423 359 429 398 413 409 421 394 364 383 386 394 423 329 397 310 385 374 366 367 402 363 402 349 365 375 377 338 404 343 388 327 353 359 377 339 340 323 373 319 353 349 313 339 315 308 345 309 300 327 312 298 310 306 351 290 304 316 298 320 282 318 289 315 326 279 286 288 310 281 298 260 300 319 278 306 271 294 302 265 303 239 258 284 271 289 261 286 252 299 249 215 253 268 268 270 245 293 252 247 256 226 221 232 233 235 238 245 265 229 227 229 251 229 258 218 223 249 255 251 223 215 223 227 273 212 229 212 227 238 206 219 227 218 232 226 220 228 215 193 214 208 206 213 205 213 217 207 190 226 216 221 217 183 194 178 189 193 178 176 192 199 221 204 197 207 173 171 179 182 187 193 178 165 207 177 185 176 168 177 165 166 169 158 175 181 152 159 171 148 167 172 155 148 185 160 190 182 128 154 175 148 179 136 171 145 145 159 163 139 144 132 170 159 159 141 170 141 184 171 154 141 145 145 149 141 143 146 139 162 192 131 127 159 160 157 122 156 156 131 142 154 134 152 151 131 131 124 164 159 133 155 138 147 155 135 154 145 146 119 148 154 137 131 105 145 124 111 158 124 135 117 138 147 120 103 157 137 144 110 117 135 153 99 97 113 116 124 127 123 121 107 110 135 99 113 113 106 110 112 117 107 124 108 91 124 96 102 108 106 101 107 98 93 115 103 99 114 94 98 88 85 120 102 97 104 102 121 87 99 98 90 123 71 92 98 92 85 82 95 88 105 102 78 77 73 94 83 85 99 91 79 88 87 86 80 88 95 75 79 85 88 76 75 98 76 
];
B = [
0 0 0
 310392 217584 92808
 564330 401595 162735
 468185 321798 146387
 434555 294771 139784
 392902 263662 129240
 350557 242548 108009
 292444 197000 95444
 270333 188517 81816
 257545 177743 79802
 435819 322421 113398
 304866 229517 75349
 314582 242958 71624
 318576 245637 72939
 312224 244762 67462
 404505 325780 78725
 369941 297393 72548
 381082 305138 75944
 369580 298202 71378
 388537 319722 68815
 425500 346439 79061
 388448 319809 68639
 392880 326239 66641
 403398 336681 66717
 401303 337748 63555
 461635 384551 77084
 433308 358940 74368
 476672 399772 76900
 421204 358037 63167
 457550 385511 72039
 490768 406649 84119
 498650 417306 81344
 506948 423557 83391
 470402 401619 68783
 629432 526915 102517
 484831 414152 70679
 510203 431658 78545
 1305937 1095584 210353
 493712 426849 66863
 624294 533648 90646
 1145023 966453 178570
 620421 530231 90190
 1032046 876289 155757
 510150 441799 68351
 629011 538755 90256
 1073395 909620 163775
 632672 544689 87983
 1040469 885507 154962
 624260 538449 85811
 1007262 860738 146524
 630945 541570 89375
 989476 844944 144532
 664373 572164 92209
 997923 855560 142363
 649578 563396 86182
 1071951 914498 157453
 945464 814121 131343
 610079 532038 78041
 938724 808822 129902
 477998 420843 57155
 85644734 77608213 8036521
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
69 6 1 1
1 30 1 0
3 47 0 1
3 63 3 4
3 66 0 1
6 264 4 8
284 222 28 25
5651 394 44 52
56428 557 93 89
257000 921 165 162
673997 1381 287 311
1239886 1970 694 711
1634831 3052 1650 1616
1968657 4840 4135 4354
3204961 7318 9327 9193
9376640 20474 22198 21970
8488707 36646 49333 49623
6085859 62196 79663 79346
4011139 101655 109407 110100
875278 146048 152913 153311
242495 194418 193356 194886
258314 237067 239803 241079
282630 300464 286738 287984
320129 350414 333211 334600
349516 403813 372886 373853
379702 442178 404126 405706
401471 464862 424217 427046
415182 469844 432055 432503
416175 456709 425059 428684
409570 429623 410565 413833
390417 395042 386765 388812
365031 361272 359941 361484
340686 335488 336410 337201
321044 316717 317745 319175
309585 304098 305303 306159
303901 297815 300030 301636
304624 297645 300506 301610
307526 302038 304818 305735
316198 310958 310827 314494
327354 320981 323273 323550
340462 335332 337288 337641
359193 353322 354602 356937
380634 374465 376841 377723
400073 395214 395817 397520
421249 413932 416091 417399
438047 432363 435087 435100
451079 446370 448498 450197
460330 457641 457595 459254
462836 460911 461090 462491
459950 457041 456414 459534
446056 446623 446439 446969
426608 426518 425049 426121
399283 399853 397789 399385
368553 367657 367293 369686
332364 333079 330632 332163
296068 296960 295862 296498
261186 259898 260090 261265
226513 228387 227333 228199
200443 199341 199284 201060
176470 176491 176584 176812
158336 158840 158970 159696
146251 145716 146744 146465
136642 136941 137092 137722
131599 130669 130282 131271
128045 127710 127438 128194
128357 127326 126625 127702
129449 129535 128746 129493
133841 133486 132993 133561
138993 138419 138251 139319
145001 145784 144932 145899
152006 151637 151161 151626
156048 156503 155874 156422
154823 154143 154136 154384
142150 142353 141945 141960
123822 124267 123227 123595
103569 102532 102348 103142
79285 79609 79630 79343
57051 56717 56422 56980
43489 43386 43750 44130
29265 29170 29106 29300
17262 17398 17367 17522
7068 6996 7074 6966
352 313 358 330
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
