A = [
685720 683836 8197276 634498 617742 594540 587900 586799 586258 575237 615388 705150 773165 856545 993180 1070807 1120421 1169182 1185474 1183609 1178355 1182873 1186322 1185866 1203123 1444480 1446921 1443615 1654876 1413925 1426182 1404124 1169046 1195231 1165701 1166601 1160334 1124589 1128206 1117023 1118668 1117122 1107985 1112422 1105141 1096596 1098441 1090018 1082234 1081315 1079648 1076541 1074716 1071066 1065694 1058829 1054992 1045983 1040235 1033759 1033540 1030476 1027585 1024239 1019245 1017216 1012291 1052608 1056091 1055497 1099389 1103771 1102554 1101608 1098258 1088414 1084155 1078718 1069254 1062956 1057476 1052717 1047422 1045964 1039966 1036127 1027555 1020505 1011726 1006223 998479 993649 987229 981381 978392 971050 964094 958330 948118 940526 932362 924733 918889 911832 909300 900288 897116 886452 880740 870819 861786 854008 849733 839488 837342 829369 822734 815430 809066 799922 791973 786284 778434 771512 764369 759468 753271 745425 740092 730549 724752 716364 709371 702919 697419 690675 684761 679530 672592 665430 658174 651860 645315 638155 632618 624842 620911 613981 608928 602541 597134 590136 583415 576902 571061 565181 560599 555055 548862 543663 538393 531359 525457 518917 516064 507731 503357 498486 492081 486681 480035 476955 471781 465305 459313 455135 449051 443881 439133 435349 428961 424145 420173 414126 409465 404498 402576 395119 391355 387505 382299 378121 373161 369147 363188 359761 354663 350997 346864 341586 337211 333582 329813 326313 320688 316181 314650 309684 306201 302272 297723 295030 291737 287774 283934 280000 276813 272813 268890 264612 262585 259844 256905 253152 249339 246193 242746 240418 236770 235358 231137 228213 226172 222578 219137 216681 212650 211571 207852 205387 202496 200417 197578 193585 191651 189341 186599 184013 182703 179478 176874 174474 170549 168877 167528 164956 162558 160896 158531 155764 153241 151929 149243 147461 145711 143636 141807 139619 137717 136556 134332 132268 130470 128781 127262 125267 123386 121678 120055 118911 117191 114169 113194 111845 110817 108640 107432 105862 103996 102698 101806 99342 98399 97077 95722 94549 93016 91708 90808 89222 87782 87028 85133 84783 83093 81844 80697 79392 78427 77609 76081 75130 74335 73000 72048 71613 70140 69018 68167 66826 66384 65146 64397 63631 62575 61634 60528 60056 59150 58387 57348 56655 55255 55163 54295 53685 52879 52011 51527 50300 49735 49043 48588 47710 47082 46172 45707 45070 44685 44079 43539 42656 42113 41631 40901 40321 39770 39100 38917 37862 37548 36978 36241 36037 35943 34847 34781 34170 33578 33825 32866 32236 32227 31542 31146 30971 29850 29761 29248 29123 28433 28258 28223 27569 27215 26826 26344 26119 25666 25586 24920 24800 24322 24102 23852 23488 23070 22786 22376 22418 22209 21678 21499 21187 20868 20447 20356 20164 19670 19707 19325 19318 18848 18792 18500 18101 17979 17783 17609 17278 17116 16657 16620 16455 16439 15884 15630 15829 15790 15449 15259 15047 14781 14654 14569 14352 14114 13800 13788 13732 13612 13405 13197 12974 12922 12937 12568 12517 12294 12367 12156 11913 11901 11770 11517 11448 11271 11245 11181 10926 10946 10676 10525 10685 10249 10255 10250 10112 9998 9936 10007 9928 9558 9497 9288 9360 9266 9139 8972 8956 8782 8939 8719 8610 8629 8623 8298 8285 8203 8397 7977 7995 7968 7748 7795 7714 7674 7620 7391 7404 7289 7199 7227 7170 7203 7153 6909 6877 6947 6913 6721 6663 6592 6662 6578 6525 6481 6378 6375 6249 6217 6055 6072 6185 5916 5940 5935 5919 5899 5739 5701 5683 5711 5604 5607 5444 5585 5459 5292 5416 5347 5283 5223 5255 5135 5276 5153 5082 5117 5055 4948 5008 4886 4852 4774 4712 4668 4760 4682 4566 4592 4568 4615 4617 4420 4469 4412 4453 4359 4353 4255 4326 4336 4200 4129 4263 4128 4221 4170 4110 4124 4072 3933 3954 4012 3918 4057 4145 3987 3866 3830 3976 3823 3832 3779 3841 3734 3717 3657 3680 3597 3667 3490 3497 3542 3616 3442 3479 3556 3411 3379 3395 3451 3380 3381 3365 3379 3289 3288 3261 3312 3141 3264 3172 3256 3219 3116 3086 3144 3086 3135 3144 2964 3008 2959 2999 3017 2954 2987 2953 2876 2961 2927 2886 2896 2814 2846 2762 2737 2838 2815 2673 2768 2798 2641 2616 2613 2590 2653 2577 2498 2634 2511 2585 2493 2468 2528 2481 2505 2569 2514 2538 2523 2457 2467 2413 2421 2387 2313 2291 2430 2399 2284 2289 2259 2263 2310 2287 2252 2257 2288 2179 2213 2204 2164 2221 2268 2220 2093 2153 2149 2064 2131 1938 1998 2117 2088 2040 1999 2022 1984 1981 2021 2026 1953 1880 1980 1917 1900 1984 1960 1915 1897 1932 1871 1950 1893 1909 1818 1803 1923 1811 1817 1773 1803 1795 1827 1689 1738 1768 1823 1774 1793 1840 1702 1677 1697 1672 1675 1657 1665 1702 1709 1592 1644 1609 1626 1589 1596 1547 1601 1570 1555 1593 1521 1616 1565 1524 1514 1572 1532 1421 1451 1554 1468 1507 1462 1452 1448 1472 1462 1470 1429 1444 1490 1442 1428 1427 1339 1420 1445 1383 1389 1440 1422 1458 1366 1349 1492 1468 1438 1567 1577 1501 1432 1454 1421 1492 1539 1453 1456 1482 1456 1369 1441 1282 1241 1223 1240 1247 1237 1198 1214 1157 1186 1214 1160 1147 1179 1175 1173 1117 1156 1218 1180 1104 1178 1105 1121 1097 1119 1117 1105 1105 1091 1012 1067 1130 1069 1057 1068 1070 1017 1029 1029 1036 1014 1053 1021 1065 1005 1004 955 1015 995 968 966 900 927 979 1026 942 971 994 996 959 937 943 957 922 977 979 975 994 1006 971 980 936 1015 1068 996 951 967 957 1018 979 952 979 1113 1074 1075 1111 1012 1004 1004 1025 991 1010 1029 990 981 1030 998 891 837 880 831 828 775 814 826 762 775 764 789 784 796 763 783 813 756 802 741 816 791 748 787 748 745 767 727 789 734 723 691 816 746 738 723 733 697 720 660 698 686 700 637 668 664 667 668 652 672 664 613 645 595 619 643 620 628 626 590 610 601 615 600 552 613 609 583 558 577 633 650 615 587 584 574 593 608 581 598 556 579 632 577 580 614 606 571 612 593 591 576 590 637 600 590 603 626 581 595 616 602 600 594 575 593 576 646 549 597 587 661 661 614 668 601 639 711 698 683 641 627 605 659 608 592 591 542 608 580 566 613 594 677 633 583 553 568 650 560 598 556 521 538 502 559 523 488 509 565 506 470 477 495 464 455 469 485 468 457 456 418 428 426 422 385 428 373 363 346 378 359 377 380 358 353 343 343 382 367 343 336 349 331 336 332 318 345 351 322 341 324 332 349 330 326 307 312 305 293 331 350 352 314 284 298 312 333 327 319 281 296 315 307 306 293 281 292 304 312 272 268 273 283 273 292 307 275 309 301 315 295 282 246 246 274 275 238 263 266 238 283 279 248 280 244 274 267 263 255 245 276 252 242 248 253 248 239 247 245 237 250 232 226 219 240 238 232 214 240 223 231 221 224 228 215 217 237 209 237 223 210 211 196 212 190 210 210 194 194 195 230 197 224 201 179 219 197 206 218 208 205 211 204 206 207 204 211 200 189 187 181 192 190 179 160 185 166 200 197 203 174 180 202 188 173 185 189 176 182 171 174 169 184 192 166 180 145 173 171 200 161 161 163 171 174 148 151 134 176 159 158 173 188 163 161 158 174 145 154 148 160 143 159 160 140 131 151 137 150 151 165 139 172 127 134 128 132 145 163 148 148 140 154 134 139 142 130 133 133 152 145 132 150 140 147 125 139 122 122 142 153 132 127 127 135 128 140 139 122 133 140 110 97 135 122 131 125 122 122 121 119 109 96 117 146 94 107 130 102 123 123 110 108 103 123 129 110 117 123 113 109 110 104 97 115 131 76 134 105 121 109 117 106 118 113 105 99 127 101 108 96 123 93 108 98 102 97 85 102 110 105 81 85 110 90 105 86 92 102 96 113 87 107 82 84 100 94 114 101 112 99 103 102 93 93 100 78 84 89 80 93 87 81 88 94 95 83 93 88 93 67 73 77 81 66 90 90 89 79 90 92 64 69 73 71 68 78 74 77 70 58 82 82 88 70 65 79 77 63 62 69 59 57 74 59 65 74 67 58 60 74 56 69 55 64 77 54 70 63 76 73 57 73 53 63 64 62 77 63 48 55 53 73 74 67 78 65 69 62 63 61 62 67 69 68 58 71 64 66 72 60 59 58 59 63 67 62 57 70 74 71 51 59 66 66 72 51 68 55 67 70 49 65 48 56 58 62 59 53 66 56 65 68 66 64 55 60 55 50 68 62 54 60 51 72 46 50 51 50 49 43 43 37 53 46 42 56 58 46 54 48 47 56 61 62 61 47 61 52 49 41 42 53 43 36 42 35 51 44 43 47 46 35 49 44 53 55 37 37 41 44 51 43 38 32 38 45 35 45 43 40 46 35 41 40 45 34 28 55 39 37 45 30 48 64 30 40 47 38 44 46 44 49 50 28 42 40 36 27 39 53 39 37 39 43 35 30 45 27 29 31 23 33 34 31 30 37 36 41 34 31 37 30 26 27 36 32 27 46 40 34 34 34 38 34 29 36 45 31 26 24 34 31 29 28 33 40 26 35 20 37 22 25 21 34 33 39 28 24 27 35 21 28 29 23 33 25 23 22 32 22 23 27 27 27 27 24 26 22 22 17 23 26 16 21 33 19 24 31 23 27 21 26 19 18 29 17 21 18 15 16 22 24 27 21 19 16 19 14 17 28 23 21 23 20 28 25 16 16 13 25 22 18 24 27 18 23 14 28 19 18 26 22 23 23 21 20 21 26 19 24 23 19 22 20 20 17 19 13 18 22 26 18 20 12 17 16 14 16 11 20 16 24 19 15 20 16 14 16 21 17 11 12 19 13 19 17 15 7 12 15 11 6 17 13 16 9 11 14 17 19 19 18 24 5 11 7 18 8 10 15 11 14 7 17 8 14 13 18 11 14 14 11 15 13 11 4 16 13 21 11 11 13 14 9 8 13 16 10 4 16 13 6 23 9 10 9 15 15 17 10 14 13 8 9 6 12 6 14 10 14 13 16 10 14 14 15 12 6 8 4 10 8 15 16 14 17 16 10 13 7 11 15 16 9 15 8 13 9 8 15 7 15 4 12 9 5 12 8 13 6 11 9 5 8 8 3 7 10 8 8 6 13 6 11 6 11 12 12 7 10 11 12 5 8 7 12 8 9 7 8 5 7 12 8 7 8 11 7 9 17 10 7 8 5 10 11 7 8 10 5 11 12 3 6 5 16 5 9 11 9 11 4 9 10 8 11 4 8 8 8 4 10 8 11 6 
];
B = [
0 0 0
 565312 308058 257254
 654983 382717 272266
 452570 264341 188229
 978206 662873 315333
 540365 364924 175441
 376683 257931 118752
 380707 267836 112871
 262331 183758 78573
 202600 143940 58660
 169744 121165 48579
 265516 195489 70027
 287498 211318 76180
 253555 184492 69063
 826465 639740 186725
 371968 284508 87460
 399778 313797 85981
 314288 246994 67294
 368330 293584 74746
 372473 297136 75337
 297367 235659 61708
 599024 485911 113113
 402158 323368 78790
 398346 322077 76269
 311618 251294 60324
 392608 318937 73671
 378935 309034 69901
 525294 428710 96584
 313084 254360 58724
 421175 343268 77907
 426086 348718 77368
 345598 281606 63992
 445234 365227 80007
 431256 353473 77783
 557486 457288 100198
 387976 317339 70637
 479130 392891 86239
 957708 781228 176480
 456352 374862 81490
 486388 398190 88198
 871958 712917 159041
 562843 463459 99384
 834334 683260 151074
 427703 351846 75857
 551817 454750 97067
 860918 705632 155286
 511576 420904 90672
 844674 693344 151330
 574116 473534 100582
 844964 694344 150620
 517990 427733 90257
 832357 685265 147092
 615532 508326 107206
 843927 695149 148778
 524211 432986 91225
 898578 740629 157949
 838802 692905 145897
 525603 435243 90360
 847270 700137 147133
 504670 421580 83090
 71949204 61605143 10344061
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
4 52 0 0
2 6 0 0
1 14 0 0
7 16 0 0
7 14 0 0
11 18 2 0
190 32 0 0
1826 31 1 2
27326 50 27 6
140034 56 86 33
325601 65 737 142
711906 118 1092 312
1385787 159 1305 568
2424376 298 1901 1068
3476172 745 2651 1855
4313903 1590 4399 3813
4287381 2752 7316 7093
3456448 4650 12062 11923
2176753 7478 18251 18620
945346 11455 26381 26486
279962 17792 34536 35049
87026 26058 43385 43630
64619 37777 53447 53586
70804 51498 64216 64695
82199 67411 76794 76666
95375 85507 90845 91439
112097 103759 106663 107081
128228 122662 124864 124656
147345 141069 142706 141966
165028 161146 162190 161590
182749 178538 179690 180252
201735 196282 196043 197051
220623 212103 211995 213756
228131 225162 225443 226749
239072 238064 238136 238133
250720 249396 249045 249132
260069 261258 259760 259907
269755 270886 269110 270718
280611 280246 280690 281621
292556 292574 291978 292002
305720 305320 303164 304851
318970 318739 319120 318537
335650 335590 333364 333515
352100 352299 350439 352328
370930 371354 371360 369959
390799 389840 390147 391602
409204 409773 407874 408193
424189 423960 423145 425267
436293 436331 435922 436657
441080 441812 441616 442971
441181 443122 441158 441857
433572 434236 433575 434933
417371 419926 417347 418649
395575 398645 396658 396937
368483 370945 369179 369681
336525 339715 338087 340127
304781 307236 305262 306947
273288 276144 274341 275550
244755 246790 245075 245999
221511 223386 222596 222458
204216 204994 205836 205421
192883 194681 193912 193854
186345 186323 186657 187685
183572 182973 183181 183581
187058 187473 186953 188084
197833 199455 198214 199384
213882 213353 212762 213835
232185 232645 232310 233172
259714 260467 259786 260127
286532 286689 286010 288124
318745 317859 317155 318529
333273 332683 332839 333465
349958 349633 349308 350431
365398 366208 364670 366550
364789 363525 363554 365100
340582 340687 340538 341491
300627 302029 300277 303634
225861 226797 226307 227349
124441 124116 124167 124894
46180 46742 46331 45877
7243 7157 7077 7214
47 42 27 54
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
