A = [
2974580 3092347 45384113 2721027 3326299 2893558 2725512 3288291 2962794 3258518 3405251 3186255 3650661 3525637 3577642 3858767 3643643 3981001 4125975 3890491 3968751 3958458 3860375 3912527 3863133 3859996 3989116 3953818 3942645 3931433 3952288 4001032 3902814 3957303 3983327 3958856 3961756 3882410 3904959 4020264 3914994 3966321 4050500 3968956 4063897 3964247 3900419 4125595 4001983 3948769 3987751 3727226 3757144 3741313 3580186 3456186 3533545 3630609 3430357 3358934 3429767 3360613 3310285 3233238 3178987 3202926 3114749 3053120 3061149 3001509 2973487 2988517 2951202 2945621 2964872 2925587 2897664 2894473 2827513 2756609 2741689 2742590 2668968 2627787 2647091 2563478 2478254 2367009 2306976 2289977 2250735 2221960 2212007 2176504 2151349 2131707 2114032 2101369 2073012 2047574 2028391 2006764 1979053 1962925 1947218 1927299 1911378 1887663 1878216 1858454 1840383 1829872 1813385 1800024 1786761 1771553 1772175 1754049 1731621 1730320 1730066 1712892 1697643 1691636 1676143 1661486 1644569 1627749 1607239 1594648 1580129 1559048 1545216 1526257 1515097 1495200 1476263 1469878 1454452 1430463 1419008 1406918 1389695 1375177 1360275 1344467 1333029 1316521 1299176 1283367 1267069 1255724 1242251 1222109 1209230 1193872 1179860 1167358 1149120 1137378 1124092 1111459 1092044 1080550 1069683 1055303 1043768 1029737 1021796 1008631 993713 985781 974935 968647 968719 948855 936320 931592 907996 895271 883019 874898 872610 857677 851478 843995 830770 824589 816136 808128 803105 791470 786621 776296 765322 757649 748362 743482 733761 724796 719203 713706 707375 700290 695115 689596 683491 676277 667409 655714 645463 633102 626151 616911 613528 606942 602582 600438 593393 588783 584836 578192 572011 564938 550328 538475 523890 512605 496016 484861 474540 467211 457817 447740 441762 435777 430701 424281 419632 413263 407763 401893 395371 390064 385142 378909 373211 368389 361950 356707 351010 346451 342472 335157 330214 325531 320810 315460 310768 305763 302737 298303 293547 288805 284087 279944 276526 272300 268122 263985 260734 256341 253161 250029 246840 242657 238808 236275 233242 228503 226037 222291 218905 215818 212333 209725 208156 203796 200679 197569 195514 192292 190045 186668 184289 181133 179431 176222 173343 171615 168942 165988 164297 161486 159265 156722 153974 151976 150531 147759 144700 143833 141859 139808 137441 134809 133126 131200 130098 128293 125350 123418 122288 120241 118634 116654 114989 113167 111902 109741 108684 106760 105406 103398 102508 100600 98908 97564 96315 94994 93454 92084 90888 89213 88527 86923 85976 84600 83401 82414 81074 79636 78254 77755 75800 74849 74090 73220 72004 70680 69628 68203 67608 66269 65608 64892 63549 62693 61688 60821 59944 58823 58093 57412 56509 55439 54525 54094 53239 52150 51391 50898 49864 49291 48653 48291 46925 46420 45655 44893 44261 43522 42870 42291 41571 41098 40375 40036 39098 38940 37782 37548 36821 36390 35954 35458 34893 34362 33664 32713 32665 32319 31945 31189 30691 30187 29942 29352 28896 28500 28164 27660 27352 26956 26296 25933 25681 25160 24816 24635 24309 24015 23408 23123 22576 21944 21959 21754 21614 21157 20537 20430 19886 19824 19495 18969 18773 18591 18118 18347 17865 17584 17164 16782 16669 16583 16076 15944 15843 15527 15391 15083 15020 14519 14414 14159 13931 13675 13507 13420 13452 13060 12928 12473 12363 12292 12183 11947 11878 11396 11462 11342 11046 10821 10590 10450 10395 10177 10113 10153 9989 9749 9602 9343 9389 9136 9092 8830 8870 8660 8657 8335 8217 8152 8045 7862 7651 7487 7555 7375 7429 7189 7235 7018 6731 6698 6689 6739 6571 6408 6254 6379 6092 6130 6001 5964 5860 5816 5795 5488 5532 5410 5271 5191 5055 5140 4953 4948 4936 4707 4653 4558 4494 4488 4427 4436 4290 4232 4080 4146 4066 4028 3940 3877 3735 3592 3698 3704 3667 3475 3629 3513 3467 3247 3238 3230 3266 3185 3087 3113 3035 3047 2926 2996 2910 2898 2812 2764 2707 2662 2606 2677 2542 2444 2534 2552 2529 2367 2516 2270 2374 2341 2286 2315 2225 2122 2180 2146 2106 2042 2058 1980 1988 1988 2050 1915 1877 1851 1874 1858 1781 1762 1782 1760 1681 1737 1612 1627 1634 1592 1556 1551 1548 1530 1501 1474 1498 1348 1474 1443 1451 1456 1383 1324 1283 1254 1347 1266 1311 1269 1247 1237 1243 1206 1221 1215 1176 1167 1141 1082 1153 1077 1056 1082 1043 1024 1064 1023 988 999 982 980 969 1046 947 927 939 922 846 908 855 842 935 865 871 833 826 848 790 793 834 809 793 772 749 732 701 762 718 729 694 685 669 706 625 699 672 649 661 598 562 586 675 603 613 621 599 592 582 544 577 573 574 568 563 586 555 591 526 536 532 509 541 498 499 523 508 539 480 504 495 479 505 468 481 513 480 475 449 456 495 470 432 447 432 432 437 401 470 453 392 407 431 393 402 403 389 402 432 404 407 373 386 368 419 344 369 423 345 350 372 363 353 453 335 335 350 321 329 315 306 287 284 329 315 318 316 312 291 294 290 287 283 281 287 300 274 289 254 287 274 270 284 257 257 256 265 274 279 289 263 266 278 271 257 264 248 233 261 246 258 259 239 264 226 263 226 245 235 220 238 211 202 225 238 233 203 224 212 224 204 223 206 195 223 205 188 229 222 195 195 184 201 196 199 204 203 194 204 196 214 191 195 195 176 193 177 191 186 163 195 144 174 178 187 191 184 190 173 162 161 149 153 182 173 122 186 143 144 163 139 158 148 149 145 169 119 155 146 134 170 159 142 125 133 140 153 138 133 138 145 149 121 157 127 152 117 149 141 140 155 143 149 135 136 126 141 125 133 139 130 116 127 119 135 122 139 143 126 137 118 123 130 112 125 123 139 143 108 99 103 124 128 135 103 116 116 108 100 127 111 123 117 109 98 110 137 116 135 126 110 130 115 118 118 115 120 102 118 137 121 94 114 105 95 116 118 98 116 113 81 95 114 99 129 117 102 120 99 106 98 115 95 89 116 96 118 115 92 85 108 98 89 98 87 82 79 97 80 81 78 94 74 99 91 79 104 93 69 82 89 71 114 90 88 96 87 88 71 94 76 89 95 93 97 99 103 94 120 119 134 164 219 303 477 551 634 671 641 671 709 710 725 741 863 593 460 457 493 501 465 455 462 453 381 400 394 415 438 427 431 408 426 445 440 428 428 439 430 425 425 469 398 392 435 402 453 419 385 402 515 437 520 504 559 751 602 625 622 572 610 673 605 579 567 2006 717 569 484 488 371 409 408 327 271 298 231 236 252 238 217 231 225 195 182 179 168 175 163 160 169 153 159 148 158 172 177 159 166 151 174 164 169 196 183 201 223 308 290 918 779 753 526 484 429 422 421 363 266 245 163 143 158 157 164 139 157 117 110 86 91 96 137 199 774 108 67 72 67 65 83 79 56 53 63 72 68 58 59 56 73 74 62 62 72 61 67 92 85 87 88 86 93 91 105 92 103 107 93 89 122 133 119 116 142 117 124 124 140 151 121 130 133 111 154 160 155 148 161 160 150 146 161 192 181 196 163 190 198 174 201 182 188 193 230 192 185 179 218 173 185 205 212 184 208 206 212 251 219 184 253 235 213 222 228 190 213 208 268 242 208 244 252 253 247 281 272 244 253 223 217 253 283 253 242 267 267 252 292 265 271 273 242 317 265 318 272 296 297 316 304 315 316 301 283 324 270 266 226 276 259 278 259 271 197 221 160 120 108 106 123 87 117 113 119 157 109 155 321 140 114 93 64 62 72 84 72 60 79 73 77 82 62 80 75 81 84 86 83 89 98 94 90 97 76 85 75 117 110 131 110 118 127 121 113 114 149 156 142 147 138 137 122 134 123 104 123 130 116 98 109 128 146 118 125 137 119 131 133 131 141 111 123 137 116 125 107 133 136 103 109 126 90 96 108 90 91 97 276 109 99 75 76 66 89 77 63 59 59 60 73 77 47 48 58 59 40 61 39 50 41 55 64 42 35 44 41 41 48 50 46 46 33 48 39 29 32 52 34 41 50 41 46 56 40 26 45 54 37 33 35 36 28 36 36 34 29 38 32 39 32 37 33 50 38 55 42 44 50 52 67 37 44 58 29 43 44 39 41 41 34 31 40 44 37 32 30 31 23 27 27 31 37 36 33 40 29 35 27 30 32 40 36 37 42 34 37 39 42 41 41 37 40 39 35 50 41 44 40 33 46 43 56 59 52 54 61 45 57 58 46 57 49 61 50 79 80 55 74 70 61 71 66 55 60 81 64 57 64 70 62 74 69 78 62 73 51 73 74 71 83 66 72 71 70 73 55 72 80 55 79 77 69 93 75 80 78 75 74 72 83 63 66 73 83 66 63 61 71 53 75 91 55 63 52 66 77 55 60 76 68 64 53 54 59 75 85 53 60 67 67 79 67 61 57 61 73 80 71 63 66 65 51 55 46 47 37 36 27 36 34 35 20 32 41 31 36 27 24 28 36 39 25 29 34 26 22 28 28 21 28 26 26 25 30 22 18 23 24 26 24 24 13 23 19 21 17 19 17 27 30 15 20 21 27 27 26 22 26 37 23 22 28 17 20 26 16 30 32 33 18 32 27 25 23 27 32 14 25 23 20 22 20 19 17 21 20 30 33 19 26 34 20 21 35 26 26 24 24 17 32 21 20 33 22 26 14 28 18 22 39 29 21 17 24 18 22 27 13 27 21 23 25 27 26 22 20 15 19 7 27 18 22 16 27 20 17 23 26 25 18 18 30 20 18 17 31 32 26 21 20 26 27 26 23 21 21 24 17 33 12 19 16 15 14 17 8 16 16 15 17 18 17 15 15 12 12 13 10 16 17 16 10 22 17 15 18 16 13 15 16 17 8 11 13 12 13 16 24 14 18 20 14 13 16 13 10 14 13 12 21 15 24 18 10 27 12 24 22 21 28 32 16 20 22 21 29 23 25 18 15 27 17 24 27 24 33 28 34 31 14 31 38 28 26 26 23 33 31 27 22 34 28 30 24 30 35 22 26 24 40 24 23 15 24 21 19 23 25 16 21 16 24 15 17 15 23 19 18 24 21 22 30 26 16 31 27 12 21 21 27 29 15 24 25 29 27 20 14 8 20 13 29 19 17 20 14 25 26 20 24 24 22 15 19 24 13 16 19 13 7 18 27 16 14 16 22 21 22 18 17 20 19 20 17 18 13 17 18 13 11 22 15 19 9 22 11 23 11 21 19 21 17 23 15 19 12 18 18 14 
];
B = [
0 0 0
 2005565 939848 1065717
 3095150 1952741 1142409
 2001200 1069863 931337
 1670837 888052 782785
 1186643 587954 598689
 1198904 702493 496411
 598449 323714 274735
 936204 594083 342121
 1241159 724689 516470
 2333585 1616433 717152
 2146525 1383958 762567
 1491941 888062 603879
 1294794 759779 535015
 1550272 990377 559895
 1878966 1301769 577197
 1320551 825235 495316
 1669994 1114347 555647
 1214374 756435 457939
 1188601 740516 448085
 1538657 1049145 489512
 1236585 790363 446222
 1229900 785715 444185
 1876007 1314819 561188
 1198731 773065 425666
 1474021 1011300 462721
 1848734 1321530 527204
 1247374 825053 422321
 1229883 819716 410167
 2089825 1547894 541931
 1413083 977373 435710
 1271160 867515 403645
 1821381 1350297 471084
 1286270 892807 393463
 1875122 1419845 455277
 1480625 1072513 408112
 1336898 954441 382457
 2397382 1902750 494632
 1527798 1152316 375482
 1771265 1387329 383936
 2613032 2132913 480119
 1810868 1437925 372943
 1720032 1327524 392508
 2365862 1966190 399672
 1550939 1205216 345723
 1525562 1142975 382587
 2438572 2056954 381618
 1451988 1095781 356207
 1166568 844577 321991
 3836867 3427176 409691
 1192268 873865 318403
 1338257 1010215 328042
 5791452 5391193 400259
 1329013 1013335 315678
 1060948 773052 287896
 9944513 9496388 448125
 1084911 793273 291638
 1041476 766448 275028
 1083058 799078 283980
 1014464 751156 263308
 185563782 172587632 12976150
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
39 66 0 0
8 14 0 0
31 45 0 0
37 41 0 0
47 40 0 0
78 45 26 0
1673 77 65 10
12485 78 93 24
174443 104 123 25
1240485 166 148 35
3065173 174 213 65
7040256 207 281 114
13881204 232 502 196
24991861 325 1267 554
35935618 502 1497 834
44293373 784 1834 1304
41731093 1395 2977 2586
31965455 2257 4681 4521
20337917 3546 7126 7096
9750388 5106 9686 9820
3161310 6851 12417 12443
578224 9141 14933 14884
57852 12735 17626 17735
24477 16129 20630 20879
27027 20691 23981 24436
30435 25311 28123 27904
34248 30314 31604 32173
38537 34831 35558 35802
41761 39031 39144 39687
44847 42571 42626 43214
48725 46061 45518 45467
50735 49294 47654 47520
51085 49649 49597 49550
52338 51161 50855 50962
53290 52874 51385 51439
54665 53000 52355 52148
54043 55008 52723 52891
55206 54344 53306 54078
55479 55499 54285 54576
56085 56068 55411 55768
57807 57851 56602 56495
59140 59009 58275 58729
61149 61447 62022 61799
62998 63000 62642 63414
66566 67015 65734 65850
69982 69917 68675 69211
71824 71988 72108 72101
75811 74827 74472 75411
77515 78263 78229 78157
80101 80794 80107 80806
82574 82728 83088 82726
82257 83026 83011 83486
82762 82709 83241 83263
80667 80939 81929 82209
78522 78642 79127 79302
75551 75784 76179 76412
72303 71973 72241 73038
67403 67514 67712 67834
62110 62261 62394 63289
57699 57998 58970 59221
53441 53445 53441 54017
50685 50868 50690 50718
46983 47631 48024 48883
45847 45774 45732 45758
45070 44893 45548 45747
45308 45212 45471 45964
47334 47650 47479 47481
52813 53726 51493 51535
50484 50843 50955 51192
54002 54120 53990 53996
56288 56497 56578 56944
58917 58539 60401 60824
60734 60256 60934 61336
59876 59486 59700 59611
57446 57101 57425 57357
56963 57491 56348 56229
50460 50546 50734 50505
40403 40615 40677 40341
38020 38047 37988 37877
34998 35326 35425 35436
20087 20511 20290 20007
12203 12050 12580 12442
793 795 825 768
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
