A = [
907963 942776 3897027 764241 792232 715363 693796 701606 680665 637936 632487 634479 626140 616276 608406 599705 591119 587486 580208 576318 572138 564478 561945 560349 562649 674406 673173 675398 788610 788791 794664 797170 801845 806162 805836 802290 793373 786533 782934 772360 768029 765141 762447 759312 758823 749053 743990 737831 729379 723109 717689 713397 710549 707205 702918 698576 692574 685205 680615 674219 667330 662765 660901 657961 648916 646302 643525 637464 633184 625258 619914 614440 609584 603242 600924 596814 591802 586771 580286 576295 572026 565342 560905 557529 551926 546818 542577 538264 534409 529559 522706 519655 514703 510672 505757 499767 497929 493462 489957 484829 480156 477103 470368 467640 464078 458980 456091 454882 447677 445464 441235 433777 431634 427635 424280 421121 416492 412465 408903 404442 401730 396870 391736 388226 383958 381248 377644 373049 370666 367235 363634 360339 356103 353308 350129 345445 341533 339550 336313 333134 329337 326528 324291 320630 317522 314467 310830 307543 305131 300937 299273 295551 292877 290126 286080 284294 281741 278801 275506 271394 269640 266280 262112 259395 256017 253369 251005 249073 244977 242614 240861 238562 234640 233232 229856 227207 225225 221945 219667 217373 215895 213230 210647 208232 205684 203788 201266 198815 197208 193798 192106 190165 187249 185649 183246 180926 179668 177714 175287 173327 171674 168737 167246 164352 163009 160759 159452 156323 155457 152728 151103 149990 148296 145642 144292 142560 141344 138912 137958 136296 134314 132755 131151 128161 127563 125037 123530 122852 120839 118504 117602 116613 114438 113013 111524 110746 108615 106874 105126 104426 103162 101620 100565 99630 98627 97111 96702 94707 93765 92651 91101 90374 88995 87609 86605 84741 83863 83048 81744 80851 80200 78100 77378 76550 75705 74301 73317 72241 71306 70548 69721 68768 67889 67242 66310 64968 64234 63539 62571 61835 61245 60700 60055 58828 58311 57487 56314 56325 55574 54283 53642 53223 51906 52270 50900 50800 49836 48684 48003 48104 47127 46631 46031 45839 45076 44400 43821 43050 42883 41649 41644 40777 40420 39421 39564 38744 37995 37820 36706 36432 36364 35289 34289 33945 33519 33389 32628 31767 31253 31008 30720 30201 29911 29770 29027 28935 28390 28125 27959 27100 27044 27003 26469 26388 25742 25333 25273 24912 24441 23746 23743 25160 23608 22904 22801 22367 24664 21655 21845 21481 21075 21053 20412 20418 19842 19692 19376 19228 18676 18581 18479 17990 17802 17712 17373 17329 17160 16844 16601 16224 16138 15873 15649 15636 15944 15300 14972 15125 14907 14581 14821 14353 14593 14379 14142 13949 13259 12845 12829 12919 12664 12400 12221 12163 11841 11824 11544 11420 11400 11206 10863 10976 10526 10728 10515 10539 10342 10070 9914 9792 9586 9535 9507 9424 9233 9118 8981 8981 8964 8990 8521 8485 8644 8410 8351 8226 8248 8088 7991 7669 7655 7477 7408 7278 7308 7100 7203 6885 6958 6860 6848 6876 6663 6744 6673 6494 6470 6524 6304 6214 5988 5986 5786 5801 5975 5809 5705 5606 5655 5691 5534 5409 5320 5413 5369 5138 5201 5180 4866 4737 4826 4983 4765 4799 4685 4770 4794 4594 4622 4598 4552 4520 4516 4408 4391 4458 4228 4260 4256 4102 4174 4113 4010 4039 3991 4004 4041 3838 4023 3804 3759 3704 3692 3702 3691 3600 3559 3492 3458 3502 3445 3344 3446 3385 3340 3324 3218 3196 3290 3295 3256 3238 3189 3110 3190 3167 3076 3154 3101 3222 3210 2992 3046 3102 3013 3262 3045 3346 3111 2808 2952 2896 2857 2835 2904 2900 2725 2818 2767 2710 2669 2815 2648 2869 2827 2458 2389 2421 2483 2319 2446 2503 2529 2602 2691 2683 2655 2462 2475 2381 2357 2280 2311 2346 2264 2215 2190 2238 2122 2181 2074 2141 2204 2240 2254 2097 2195 2142 2165 2122 1970 1949 2026 2004 2013 1900 1893 1905 1867 1840 1934 1892 1909 1829 1783 1732 1867 1790 1817 1797 1639 1667 1708 1663 1636 1624 1612 1659 1662 1657 1593 1624 1622 1625 1541 1555 1588 1571 1510 1608 1541 1545 1496 1530 1460 1421 1425 1382 1367 1399 1431 1404 1390 1451 1359 1440 1328 1345 1328 1433 1391 1339 1355 1302 1344 1352 1385 1278 1269 1253 1273 1316 1239 1240 1193 1199 1210 1232 1248 1207 1155 1214 1217 1117 1152 1146 1101 1134 1146 1166 1186 1230 1152 1179 1104 1112 1158 1075 1102 1149 1105 1080 1081 1037 1099 1143 1127 1073 1078 1018 1048 1034 1024 1057 1011 960 1016 1008 1088 1120 1069 1087 1099 1078 1044 1061 987 1012 1026 1039 1033 1110 1123 1143 1207 1453 1428 1177 1231 1231 1106 1056 1130 1192 1031 1056 1223 1063 1134 1077 1044 1151 1042 1054 968 961 965 1007 888 879 888 824 801 875 851 841 898 897 861 928 943 951 868 1076 903 930 841 909 852 819 795 886 852 841 860 838 851 927 754 809 761 803 705 834 765 786 794 760 809 799 782 700 722 766 816 745 725 728 795 662 644 671 704 684 680 689 624 709 665 688 658 628 660 629 599 691 651 614 627 608 629 665 707 649 672 700 681 679 643 643 716 736 695 638 628 618 622 594 602 633 596 584 623 590 603 601 574 550 541 554 553 534 479 483 527 515 517 513 540 496 485 523 563 584 562 544 606 581 535 576 529 565 549 578 536 507 463 532 509 487 512 489 485 495 479 430 508 468 470 476 424 426 417 410 475 456 476 469 419 447 453 406 416 427 439 449 438 444 485 467 704 465 444 428 465 431 398 433 410 402 411 435 376 374 372 343 362 343 404 385 380 383 346 358 313 349 366 416 352 342 347 354 378 365 373 372 359 383 342 362 342 318 318 312 296 308 351 281 291 293 295 308 303 280 306 274 264 296 280 259 348 343 293 303 304 302 312 289 289 316 302 273 251 319 302 299 303 289 283 324 295 296 269 267 292 285 301 271 274 297 248 247 237 264 264 253 285 262 278 297 228 254 283 262 289 254 257 240 269 241 269 261 281 261 264 261 250 273 244 233 272 240 246 238 233 281 297 267 257 259 245 275 232 229 247 275 288 263 273 274 242 255 279 259 240 274 255 246 273 246 263 233 288 254 226 235 229 240 210 220 228 232 240 212 223 258 194 235 227 250 217 215 231 206 226 226 231 209 176 219 211 245 217 198 169 215 224 209 217 187 207 205 191 189 222 206 211 208 187 232 195 201 178 230 203 214 209 214 205 209 199 195 222 207 180 198 194 203 186 202 196 172 210 200 169 178 181 181 212 183 188 182 200 197 179 198 175 202 191 185 184 173 177 169 215 188 199 183 173 229 196 194 198 181 195 185 187 171 204 186 183 174 199 178 209 159 214 207 195 177 148 183 155 181 160 179 174 160 186 155 149 173 154 125 141 146 124 131 122 127 135 139 142 107 136 160 145 158 157 126 126 134 125 121 115 139 132 131 132 127 135 137 137 111 126 110 122 106 125 121 118 118 132 118 137 95 143 116 121 117 118 117 111 106 128 124 122 111 130 142 115 129 129 133 120 125 97 122 93 121 117 132 108 114 110 95 111 107 104 123 109 115 103 111 139 121 112 111 104 109 120 125 138 131 113 142 107 132 103 121 111 113 102 93 107 96 97 133 117 107 94 101 91 90 109 85 100 76 103 106 98 127 91 82 91 83 82 82 83 87 89 87 90 81 82 86 75 94 73 78 94 103 85 73 76 63 82 89 105 80 84 88 86 74 78 101 90 79 76 87 91 72 94 78 67 95 84 77 79 82 68 88 85 71 59 65 64 66 85 59 89 66 78 84 86 73 70 77 88 75 86 69 85 85 76 70 86 84 85 58 64 82 76 63 84 84 85 86 104 95 104 88 106 113 94 127 117 105 103 97 98 101 85 91 93 101 99 72 81 94 93 96 76 82 97 86 65 94 84 73 82 81 93 78 77 80 95 74 84 51 63 74 62 84 63 61 80 65 65 71 64 60 70 76 70 73 66 46 67 68 59 56 61 54 52 52 57 64 58 55 58 61 47 49 43 58 62 61 51 40 42 61 56 54 59 62 63 63 57 52 59 58 60 65 69 64 60 75 66 60 51 51 73 54 53 62 53 58 68 56 58 68 60 54 57 59 53 47 38 50 56 55 63 42 57 45 48 58 58 50 51 44 67 39 55 46 50 58 54 43 42 45 46 52 39 46 43 37 53 38 31 49 52 53 64 37 58 44 52 39 42 42 31 35 36 45 38 43 39 41 46 36 49 53 38 37 33 40 38 52 48 39 58 53 51 57 50 47 45 72 47 59 52 57 51 62 68 54 56 61 51 45 49 49 46 54 57 45 54 55 53 59 45 54 41 43 36 50 60 43 49 62 58 76 57 58 66 65 56 56 40 60 57 53 37 37 33 37 40 44 43 37 32 34 45 41 37 54 47 46 46 54 44 36 36 42 51 42 53 42 53 49 51 59 67 44 50 132 211 250 263 198 164 141 171 73 42 43 42 38 35 47 35 41 44 34 35 46 46 38 27 49 50 46 43 43 49 29 46 35 33 50 55 64 89 55 59 76 48 75 55 43 36 39 32 38 28 30 35 33 22 29 37 26 36 35 35 36 35 45 43 25 28 44 44 40 27 26 32 42 38 30 36 35 44 31 40 32 33 40 37 46 29 34 32 40 33 33 32 28 35 42 37 53 44 37 38 46 35 33 47 42 35 33 33 21 33 28 22 28 28 38 26 32 39 29 28 23 33 22 24 27 26 26 31 22 25 36 33 27 35 17 21 22 28 28 25 23 35 39 30 27 31 39 27 31 34 29 30 30 28 22 25 40 35 43 35 31 31 32 32 42 33 31 38 36 28 34 22 44 34 37 31 39 34 23 38 31 21 34 35 41 40 52 35 35 31 37 35 39 47 32 30 38 35 28 33 27 33 37 34 30 37 40 24 31 25 28 29 27 27 34 17 31 33 25 42 31 34 27 33 43 40 37 22 31 31 27 29 28 18 29 21 18 23 37 24 34 23 42 23 23 32 20 39 19 32 27 31 31 21 19 24 25 16 32 21 24 20 18 32 27 24 27 23 30 29 26 25 21 23 30 24 30 18 23 24 38 35 23 29 33 32 22 33 31 15 30 28 35 25 35 34 26 36 34 18 25 25 29 38 34 32 25 32 22 32 23 31 25 23 30 30 28 22 35 28 27 28 22 
];
B = [
0 0 0
 310230 90960 219270
 148572 43610 104962
 515305 174317 340988
 327366 100563 226803
 192940 57522 135418
 506760 177215 329545
 401802 128964 272838
 224719 69714 155005
 686305 236691 449614
 713658 230515 483143
 128193 39107 89086
 2049186 713252 1335934
 271786 91541 180245
 86697 27953 58744
 477240 193713 283527
 152565 58583 93982
 46413 16066 30347
 528450 217187 311263
 42494 14416 28078
 44399 15930 28469
 10477 3766 6711
 264 83 181
 10288 3993 6295
 784608 330390 454218
 50849 18039 32810
 66465 25645 40820
 821806 353222 468584
 47445 19180 28265
 100799 40805 59994
 1282241 528068 754173
 93726 37750 55976
 167022 69058 97964
 929907 418105 511802
 616513 275480 341033
 1028117 466354 561763
 1902672 863390 1039282
 1531032 653515 877517
 951362 424269 527093
 2224175 1029541 1194634
 859558 357887 501671
 59379 24962 34417
 2030585 930546 1100039
 31849 13436 18413
 56623 23711 32912
 2784809 1316929 1467880
 58980 25437 33543
 691800 289881 401919
 3871927 1961187 1910740
 689429 296427 393002
 20 9 11
 26835856 14111831 12724025
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
88 144 1 2
78 23 0 0
233 35 1 1
334 37 2 0
266 45 1 0
221 52 39 2
482 117 124 19
2066 142 158 42
11014 150 224 84
42823 235 340 134
96647 277 406 198
202965 400 571 321
398998 480 824 523
813078 674 1140 772
1501753 942 1483 1240
2508957 1353 2165 1897
3148134 2067 3024 2812
2856258 3244 3888 3993
1980705 5098 5166 5175
1056250 6898 6353 6301
416631 8627 7267 7245
102522 10228 7639 7788
23309 10356 8123 7923
16298 9522 8442 8212
14373 9904 8447 8823
13503 10883 8512 8787
13447 9799 8973 9047
12657 9972 9384 9585
12766 10655 10249 10155
12636 11155 10746 10513
12973 11578 11363 11535
14190 12740 12188 12415
15721 14574 13299 13289
17323 15544 14579 14741
18463 16976 16353 16491
19806 18693 18135 17863
22302 20623 20159 20554
24384 23218 22837 22883
26605 25969 25717 25696
29387 28958 29091 29228
33242 33001 32987 32959
37403 37061 37341 37198
42136 42207 41907 41937
47900 47985 48022 47722
54401 54524 54066 54358
61380 61649 61877 62734
69259 69515 69754 69480
78032 77485 77682 77297
86492 86146 86381 86653
95952 95318 95664 94708
103828 103733 103848 103259
110446 110417 110268 110793
116854 117093 117319 115947
122928 122952 122392 123317
129439 128711 129839 129299
133996 134441 133767 133923
141743 142006 141795 141177
149118 148671 148074 148163
155633 154334 155101 154470
160829 160756 160817 161560
167839 168336 167362 167162
169005 168251 168427 168168
162046 160937 161953 161040
139973 141490 141208 141685
104901 105563 105570 103506
59268 59811 59595 58413
25831 27069 26508 25624
15619 15434 15749 14354
13349 11911 12356 11812
10715 11207 12753 10130
8187 8402 7965 8457
6095 4970 5523 5872
477 483 392 356
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
