A = [
465549 471918 2335639 472222 432465 425796 432066 429745 436216 426067 443645 445795 451833 455427 459403 468415 472717 477690 480951 482012 491896 493502 499836 506430 528824 620121 627287 647617 736999 737720 743896 751871 755426 767526 770196 762799 751445 746124 736074 725557 725870 717547 714135 715573 702800 696886 699710 690973 680277 674603 672754 663019 656183 650294 645542 642810 633569 630219 625479 621346 613928 613389 605031 596798 592615 581775 576324 575287 569554 561854 560576 555256 544858 542110 535283 530707 528113 518988 510621 507906 500544 493302 491535 481381 478275 477182 471104 466017 463502 452479 442978 442535 438009 433562 435485 425709 416814 415032 409674 406008 403178 399364 388583 388852 380474 377453 373855 368199 364987 361408 360074 353835 349565 346150 340374 335248 328394 324367 318183 312591 312062 306309 299587 295499 293914 287940 283186 281702 274005 273116 270257 263208 260959 261278 255377 251150 253192 246165 241543 240317 236159 231577 228733 224018 223624 221550 214874 213193 211083 206879 206443 201516 199948 196321 195470 193458 190773 187528 185273 184044 181624 177486 176207 175849 169539 165527 165202 162296 161929 159647 156967 153778 151337 148836 147472 143854 140823 139428 139201 135906 133344 133697 130694 126849 126351 126580 125452 123558 121492 119390 119065 114431 112689 112672 112149 109815 106846 104891 106090 104063 102735 100530 100010 97563 95732 95802 94143 93514 91468 88641 87514 87538 87218 86913 84091 82632 80654 80481 80024 77806 75349 73734 72868 71776 71760 72047 68917 67527 67303 65636 64563 63189 62945 62205 59986 59876 58166 57228 57537 56697 55919 54015 53063 52399 50973 51124 49500 48594 47856 47718 47301 45805 45701 44890 43930 42979 43025 42323 41081 40375 39159 38395 37775 38348 37666 36177 34794 34338 34493 34086 33648 33603 32921 31690 31756 30809 30474 29213 28879 28188 27885 26948 27102 26333 25972 25373 25273 25080 25024 24451 23629 23605 23382 22567 22382 22287 22174 22073 21717 21221 20045 19482 19050 18752 18000 17937 17564 17600 16961 16683 16001 15924 15625 15844 15670 15025 14905 14273 14189 14072 13640 13725 13280 13361 13371 13082 12928 12453 12368 12072 12242 11818 11856 11244 10895 11030 10891 10387 10146 10176 10015 9582 9346 9396 8968 8711 8619 8059 7999 8132 7844 8016 7717 7605 7511 7631 8000 7356 7200 7013 6965 6704 6602 6421 6572 6231 6080 6196 6032 6025 5978 5756 5811 6110 5756 5469 5398 5193 5160 5283 5115 4974 4764 4789 4690 4514 4519 4565 4333 4270 4432 4328 4069 4037 3892 4092 3751 3911 3912 3647 3710 3569 3458 3478 3442 3214 3207 3115 3180 3160 2957 3094 2873 2981 2858 2787 2723 2728 2733 2759 2655 2527 2678 2560 2365 2483 2480 2343 2203 2240 2221 2239 2222 2100 2107 2099 2066 1942 2016 1931 2000 1969 1901 1705 1717 1719 1710 1749 1705 1705 1663 1631 1569 1549 1546 1534 1556 1412 1389 1462 1482 1361 1488 1383 1341 1287 1301 1295 1352 1375 1315 1224 1273 1242 1157 1143 1232 1177 1079 1111 1075 1147 1051 997 1024 985 1004 1004 1031 900 949 958 924 899 909 832 882 884 884 867 821 880 802 795 820 815 731 746 770 714 757 791 755 763 692 685 698 746 673 716 676 636 643 678 663 572 584 667 603 616 570 566 569 516 575 554 547 536 509 566 531 498 545 506 498 483 519 524 507 544 532 491 498 409 441 458 522 491 496 457 509 393 544 493 497 455 461 420 484 495 406 408 419 432 446 389 436 399 435 399 472 443 376 357 366 384 370 428 343 365 367 349 319 323 359 338 357 345 358 352 341 274 279 266 285 329 281 324 277 267 241 265 260 245 266 224 267 244 257 261 229 218 212 202 213 225 227 219 209 267 234 202 206 217 174 149 176 180 160 157 182 211 213 223 148 172 157 176 137 138 139 135 138 168 154 182 176 138 126 147 139 141 133 178 187 172 134 143 130 148 146 106 123 111 106 89 119 78 88 87 107 126 92 101 95 113 77 92 73 98 99 99 104 80 105 80 94 90 100 88 103 104 82 96 103 82 83 75 80 80 99 86 73 82 103 114 78 85 89 65 66 93 78 70 46 51 67 46 60 52 51 55 60 72 97 69 78 87 85 108 95 76 79 78 74 114 72 82 82 82 87 73 78 56 72 71 74 72 66 101 65 64 62 46 33 27 46 38 44 38 32 38 52 40 63 52 46 50 64 65 31 50 34 57 127 66 73 74 56 81 96 23 45 29 28 21 11 33 30 24 28 28 27 28 22 17 20 23 16 22 17 20 21 28 20 23 23 33 19 13 20 27 20 22 22 23 21 33 43 34 40 55 44 45 59 43 90 51 45 43 49 39 14 36 24 16 15 17 13 17 18 17 28 23 25 31 22 34 31 22 16 47 35 19 33 36 21 17 22 22 14 23 33 33 27 24 21 28 25 21 24 21 13 20 13 12 8 7 11 9 8 7 8 25 26 15 18 31 24 14 23 25 18 37 15 20 20 9 7 10 9 24 9 13 13 25 25 11 1 10 17 10 18 9 14 13 13 19 11 11 4 7 14 14 12 7 8 11 10 6 10 5 18 9 14 13 12 17 19 10 22 6 19 5 6 8 12 22 18 17 15 10 6 17 12 10 19 16 10 7 9 13 12 16 14 13 14 16 20 29 13 13 13 4 10 9 5 13 11 12 8 17 12 10 15 7 4 7 8 13 12 16 8 11 9 11 5 11 10 17 7 11 18 18 3 16 17 7 9 13 13 17 7 5 9 5 7 8 5 1 5 10 4 4 12 12 10 5 5 11 5 2 7 3 9 5 3 3 8 8 7 11 5 6 3 3 8 6 6 7 4 1 6 7 6 6 5 5 2 2 2 8 3 3 5 7 4 3 2 10 11 1 3 8 8 6 3 6 17 4 5 9 9 16 8 6 14 4 4 10 9 9 9 11 11 15 6 5 20 16 14 11 9 18 8 9 7 7 8 6 7 8 17 6 9 4 11 11 8 5 2 3 6 11 0 11 4 7 6 5 10 2 6 3 6 8 2 2 4 4 4 8 5 2 5 2 4 1 6 0 6 5 4 3 8 6 0 4 2 0 2 4 7 3 2 6 10 2 0 3 2 1 3 2 1 5 2 2 5 5 2 3 11 3 3 3 8 2 5 2 1 4 14 8 2 2 1 4 5 4 7 5 5 3 6 5 2 4 1 5 3 2 5 0 0 2 1 0 3 3 5 8 3 1 2 1 0 0 2 1 3 0 1 0 0 1 0 1 1 4 2 2 3 1 2 10 4 2 0 4 3 3 5 0 7 0 2 0 4 4 0 3 7 9 4 2 5 5 6 5 2 3 0 1 2 0 1 1 0 0 4 1 1 2 7 1 1 2 0 1 1 3 6 1 1 0 0 1 0 0 0 2 2 3 2 0 0 1 0 1 0 3 0 0 0 0 0 0 0 0 2 0 0 0 1 0 0 0 0 1 1 0 1 0 0 0 2 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 4 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 3 0 0 0 0 0 0 1 0 0 1 0 0 0 0 2 0 1 0 0 0 0 0 0 0 0 1 0 0 5 0 0 1 0 0 0 3 0 3 5 1 0 3 3 3 0 3 0 1 0 0 0 0 1 1 0 0 1 0 1 0 2 0 0 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 4 1 2 2 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
];
B = [
0 0 0
 26033 5051 20982
 16924 4378 12546
 56923 17418 39505
 12016 1864 10152
 11792 2301 9491
 20022 3949 16073
 20097 4407 15690
 25173 7028 18145
 49728 17072 32656
 12197 2037 10160
 13778 2672 11106
 14189 2874 11315
 30556 7930 22626
 15223 3773 11450
 48818 17109 31709
 16696 3477 13219
 19127 4631 14496
 24196 5303 18893
 50788 12716 38072
 33403 8122 25281
 68867 21987 46880
 51667 9445 42222
 31693 6079 25614
 83076 20168 62908
 96829 23721 73108
 14292 4121 10171
 323311 105114 218197
 2137 786 1351
 9976 4023 5953
 4855 1676 3179
 7939 3123 4816
 4519 1624 2895
 39793 18494 21299
 3580 1593 1987
 9780 4166 5614
 4488 1534 2954
 7095 2733 4362
 1231 470 761
 41843 18741 23102
 8 6 2
 71 27 44
 981 397 584
 9726 3904 5822
 1101 464 637
 914 399 515
 2198 705 1493
 2826 1049 1777
 66132 31475 34657
 74 40 34
 1711 976 735
 1144 483 661
 1051 412 639
 4376 1918 2458
 67597 32817 34780
 2811 1508 1303
 3223 1792 1431
 10559 7008 3551
 410784 262051 148733
 23828 14467 9361
 42370258 31413489 10956769
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
8 38 0 0
2 4 0 0
4 7 0 0
8 11 0 0
3 17 2 0
24 14 109 10
589 20 294 45
3787 30 367 77
27957 40 519 132
132264 75 900 274
331448 69 1215 324
707046 130 1660 686
1278775 199 2243 1071
2165813 434 3418 1733
3140384 740 4833 3419
4077353 1473 6892 6055
4268987 2368 10696 9253
3548365 3822 14953 12552
2234952 5850 16988 15464
933717 9151 19647 18780
229147 14007 23470 22949
46646 19872 27010 26289
36546 26460 31666 30678
39534 33743 36309 34890
42670 39795 42537 42169
52220 46093 46908 47690
52861 52139 53246 51446
59228 58985 57374 57265
62553 62170 62318 62467
66580 66382 65084 64086
67362 69399 68287 66685
74027 71483 72837 69072
75903 73476 73483 72524
73581 74624 74810 73167
77749 78261 76945 75584
77953 78076 78871 77733
81401 79484 80924 79885
79514 80096 81038 78277
81286 82296 82525 79165
79996 82699 82607 81053
81510 83433 84407 80461
90778 89587 91780 87870
92462 90596 92307 91153
88776 107963 90310 87218
76465 75069 75153 76903
60395 57981 58935 58612
56826 57405 57220 57287
58895 58584 58506 58553
59395 59683 59919 59886
59770 59002 59016 59792
58136 57958 58250 57833
55278 55679 55667 54827
50631 50590 50357 50462
42630 42480 42139 42138
31000 31092 31216 30795
20521 20460 20578 20474
13522 13443 13424 13280
9160 9072 9228 9132
6011 6020 6072 5934
3445 3546 3438 3437
441 420 402 407
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
