A = [
730567 712422 4108961 667177 639435 605636 604020 600944 605498 592923 620267 689579 824294 946671 1061522 1189581 1271646 1312088 1313705 1291807 1260612 1260572 1264627 1242824 1250750 1522215 1519214 1512908 1743210 1454533 1454697 1432607 1156631 1162142 1151749 1154904 1148124 1130870 1123105 1132482 1137592 1141771 1143598 1158525 1163741 1161316 1153800 1152826 1172901 1166519 1162518 1158941 1162552 1170680 1153818 1146969 1141410 1148540 1144753 1121130 1125719 1133514 1123910 1118933 1118995 1117197 1103489 1094727 1086375 1078560 1073723 1074445 1079425 1076437 1075909 1069914 1062275 1055003 1039742 1029901 1025929 1019231 1009962 999927 996493 984783 967745 946835 935892 928306 921624 913003 905008 900085 894224 886151 879853 874204 867402 859162 851845 846333 840779 835707 829775 828300 821486 816104 809959 805440 798317 792485 790788 787165 783187 784965 780145 797373 802303 804437 825182 831562 835695 834661 835238 834307 829707 826672 821074 813536 811495 804961 800350 797876 796525 792762 789169 784382 782398 778186 772880 768857 764495 761010 757129 753806 751017 747623 742018 740139 733802 731070 727032 722855 722760 716182 713017 711097 707335 702548 697524 692429 689749 684838 680799 678848 675717 672729 669742 665092 659781 657031 652215 650271 646953 644723 643058 639533 635486 632337 629623 625727 622589 620313 617688 615202 611788 609894 608896 605058 602335 599269 595255 593471 589818 587300 584827 581968 580955 576860 573055 571762 569135 564922 562351 560474 558193 556214 552986 550125 544350 540450 536786 533041 530313 527978 524951 524018 520713 519872 515780 511986 508142 507193 502873 497705 495234 488967 483352 480522 476379 472050 467011 465270 459694 455955 451457 448508 445012 440807 436870 435252 430898 428545 422606 420958 417830 414822 410767 408460 405272 400766 398084 393907 390361 386837 384051 379838 376954 374261 371920 367581 363400 359705 357002 354034 350187 348072 344945 341338 339211 335878 331559 329476 325805 322452 319545 316268 312597 309682 306812 305124 300942 298872 294270 290952 288496 285899 281098 280451 275701 273038 270737 267498 263880 261783 258466 256025 252713 250122 247874 244621 241867 239049 234969 233231 229869 228448 225015 222799 218759 216659 213645 210965 208776 205553 203741 200904 198026 197029 193306 190787 189279 185671 183658 181841 177625 175763 173681 170932 169246 166587 165184 162756 160850 157620 156160 153635 150482 149453 147650 144263 142851 140539 137865 136985 134694 131954 130791 128690 126371 125140 122625 121908 118955 117824 115900 113748 112104 109825 107413 106663 105098 103556 101486 100387 98846 96488 95117 93599 92020 90471 88228 86971 85509 84313 83401 81725 80171 78951 77193 76315 74859 73210 71787 70892 69490 68380 66590 65416 64781 63402 61999 60894 59605 58841 57414 56224 55960 54586 53219 52287 51373 50543 49661 48220 47852 46703 45168 44648 43614 43189 42193 41091 40406 40004 39141 38248 37046 36461 35770 34889 34673 33687 33046 32332 31832 31082 30392 29990 29163 28786 27658 27736 26968 26018 26107 25447 24568 23890 23519 22929 22879 22086 22047 21198 20985 20420 20035 19630 18893 18675 18228 17808 17641 17294 16522 16159 16126 15623 15245 15044 14705 14436 13997 13784 13482 13156 13059 12739 12488 12335 11835 11704 11413 11251 10863 10770 10377 10082 10268 9783 9804 9416 9312 9193 8896 8733 8650 8358 8240 8018 7931 7572 7588 7602 7324 6981 7044 6666 6569 6647 6420 6134 6036 6158 5875 5735 5676 5637 5500 5378 5188 5229 4948 4967 4794 4738 4733 4562 4470 4367 4359 4065 4121 4029 4132 3894 3864 3767 3771 3641 3659 3468 3390 3355 3289 3369 3266 3229 3038 3058 2964 3123 2884 2998 2787 2788 2682 2528 2648 2581 2533 2411 2450 2456 2385 2307 2319 2228 2233 2290 2100 2114 2073 2142 1948 1933 1995 1940 1916 1891 1882 1824 1787 1642 1695 1729 1764 1591 1696 1611 1617 1558 1449 1560 1482 1532 1464 1432 1407 1337 1357 1423 1437 1322 1251 1280 1352 1244 1232 1217 1184 1256 1140 1208 1169 1156 1137 1140 1102 1006 1057 1039 998 1047 1012 1006 947 915 960 917 930 918 850 856 876 877 850 881 886 848 877 842 787 825 746 831 788 686 806 777 787 721 808 691 703 699 710 730 694 694 646 614 640 675 647 698 613 632 615 633 604 630 658 585 605 626 569 607 505 572 534 524 539 531 539 517 553 497 492 500 503 497 470 438 471 488 465 436 427 446 401 418 428 412 411 403 413 410 375 435 370 367 407 396 385 416 405 412 365 400 327 357 366 355 343 363 354 328 336 374 333 338 321 389 350 337 373 317 385 344 352 332 384 373 326 334 302 350 313 314 319 323 334 294 312 326 305 303 312 305 311 311 328 310 282 301 292 259 283 286 252 290 241 268 259 229 238 230 241 242 225 238 248 251 212 270 229 235 216 229 249 215 211 221 224 224 248 223 217 212 247 204 210 223 217 210 212 223 193 197 210 198 213 237 236 225 230 231 210 241 193 186 203 224 224 196 194 202 202 197 223 194 187 205 188 193 221 189 187 188 196 183 197 203 175 179 178 194 169 171 164 185 176 163 186 175 167 192 199 165 176 173 156 157 155 173 143 172 163 155 148 140 146 156 164 149 133 149 144 119 148 143 132 149 146 147 145 154 140 179 143 139 131 158 151 121 151 118 143 131 131 140 156 140 142 128 121 144 131 121 125 140 132 113 133 126 122 147 131 131 135 138 117 116 139 108 147 110 131 104 114 94 142 115 118 117 122 128 107 96 125 100 89 115 129 97 93 109 114 102 103 125 83 108 103 95 104 90 94 90 88 102 101 94 113 79 74 99 96 93 91 102 97 102 105 82 81 82 99 86 74 80 79 92 76 78 75 86 81 71 76 87 97 88 82 83 83 72 77 83 79 80 77 71 91 66 73 89 108 94 90 83 78 91 94 80 81 82 82 103 71 85 88 89 80 91 92 72 95 70 70 87 63 78 106 79 74 63 91 90 71 70 78 88 70 81 71 92 70 83 81 82 76 62 72 66 57 87 70 71 66 84 66 71 81 74 71 76 89 65 71 64 72 75 65 76 58 76 64 78 70 59 71 73 60 70 69 58 61 66 71 56 69 69 59 58 60 66 75 72 76 64 57 62 69 68 60 76 66 53 56 50 48 68 56 48 53 44 55 47 47 45 45 54 53 52 65 38 50 41 43 49 54 53 43 60 38 59 58 61 55 52 53 75 60 66 72 52 61 56 62 61 66 55 71 64 62 47 48 69 48 56 46 56 55 120 46 47 43 49 54 48 56 52 43 52 42 51 53 58 49 36 46 37 46 51 41 48 54 49 44 47 38 54 41 43 44 29 53 36 44 38 45 45 42 53 34 58 51 30 39 56 51 66 64 60 59 58 66 57 68 53 52 77 67 76 68 78 81 72 64 72 57 63 63 62 56 57 68 68 66 59 71 74 73 68 51 50 81 69 75 54 67 59 65 64 65 76 76 56 58 63 75 85 67 71 61 110 98 90 103 108 125 88 122 75 86 66 82 82 72 94 81 66 74 80 89 70 61 64 63 69 67 75 73 61 64 72 61 62 66 67 63 65 61 55 72 70 69 65 70 80 80 72 89 71 73 99 110 87 98 80 138 110 124 121 82 137 89 107 73 82 102 129 88 127 83 108 100 122 73 58 72 64 45 45 50 47 51 54 34 42 51 41 44 47 52 52 41 39 42 33 42 29 41 45 39 44 39 48 43 49 38 32 36 34 36 42 59 56 53 45 36 41 24 40 39 38 43 30 34 36 34 36 37 43 29 29 40 29 28 33 30 28 29 27 39 33 27 28 37 34 38 23 30 25 35 43 36 28 32 27 50 38 38 52 28 23 46 38 32 33 32 30 55 43 44 43 43 50 48 55 42 55 60 44 43 66 51 40 70 35 65 50 44 49 66 64 78 62 65 65 65 63 60 84 90 71 76 79 82 113 70 121 78 60 80 59 66 103 60 60 61 68 47 67 60 52 76 71 60 95 74 78 80 137 1274 88 119 92 130 148 112 116 157 97 131 88 115 83 98 94 131 114 80 115 90 72 154 114 114 70 104 70 67 62 65 95 57 81 63 47 69 66 58 58 61 68 60 60 43 35 70 63 51 58 38 44 54 59 58 71 52 56 45 42 63 50 62 52 62 63 65 56 56 83 107 77 59 63 54 51 53 55 43 60 54 48 59 60 48 64 63 62 48 54 55 52 53 51 45 55 49 41 56 36 55 44 36 48 31 17 25 31 34 27 25 29 32 35 20 19 33 24 24 33 23 28 27 27 31 12 32 34 28 33 33 28 30 32 33 24 22 36 25 17 30 25 27 25 21 19 30 20 31 26 24 20 37 29 23 19 25 21 27 12 25 27 23 21 22 17 23 28 24 29 31 25 21 16 40 15 23 31 18 23 21 22 18 20 23 21 23 20 20 20 23 15 26 19 11 16 15 17 14 6 7 10 18 13 18 20 10 15 25 15 16 28 10 15 19 14 14 24 23 12 9 19 18 12 13 16 18 19 17 17 17 18 12 11 14 18 15 14 10 12 8 12 16 15 15 15 8 8 3 10 6 11 10 9 2 8 4 4 6 4 2 5 4 6 10 10 7 4 5 7 12 6 6 11 6 6 3 11 11 6 5 4 7 6 4 6 8 8 10 5 7 6 6 7 5 4 7 6 3 8 5 4 5 6 3 7 5 8 9 3 4 4 8 8 8 6 12 6 8 11 7 6 8 7 4 7 5 9 12 7 6 7 9 4 9 6 9 7 4 6 4 6 4 5 8 3 9 6 6 10 5 1 5 8 4 3 5 5 4 8 11 5 3 6 5 3 7 5 11 3 1 10 6 2 5 10 6 5 12 5 6 5 9 7 4 5 5 6 10 11 7 7 7 11 8 14 7 6 9 7 7 5 12 11 5 6 3 7 9 10 6 10 4 3 6 6 6 5 4 10 4 9 3 8 11 11 5 5 7 5 10 2 7 8 11 5 4 4 9 10 4 7 6 7 10 7 6 8 5 12 7 5 3 6 5 5 3 4 5 2 8 3 2 7 1 8 3 7 5 4 4 4 6 7 4 6 3 1 6 7 9 2 3 5 3 6 4 4 5 1 4 3 3 3 5 3 10 4 8 7 6 5 5 5 10 3 7 5 12 4 7 3 
];
B = [
0 0 0
 372259 253682 118577
 878439 642206 236233
 519399 378578 140821
 430952 318025 112927
 361369 270957 90412
 284321 215256 69065
 255910 196305 59605
 271492 210189 61303
 278744 218202 60542
 660002 526277 133725
 393511 312202 81309
 355224 284683 70541
 344683 275847 68836
 332152 267470 64682
 538615 439103 99512
 403368 327242 76126
 407116 333275 73841
 368738 301742 66996
 384155 314903 69252
 491251 405332 85919
 435462 357866 77596
 431094 355890 75204
 426494 352627 73867
 420387 348228 72159
 500439 416185 84254
 440220 365406 74814
 475869 395641 80228
 430184 357894 72290
 462297 385735 76562
 493967 413225 80742
 487626 406886 80740
 487156 406548 80608
 468753 392435 76318
 552419 463118 89301
 499406 418633 80773
 504510 421974 82536
 947586 796709 150877
 491302 412441 78861
 577378 485109 92269
 883839 743616 140223
 570272 479181 91091
 830969 699404 131565
 508834 428104 80730
 582302 489955 92347
 863420 727402 136018
 593901 499976 93925
 842091 708925 133166
 585026 492959 92067
 831396 700294 131102
 590813 497677 93136
 831047 700469 130578
 611462 515408 96054
 828818 697861 130957
 598198 505653 92545
 877773 740209 137564
 790945 666785 124160
 575793 486306 89487
 803048 678133 124915
 476518 402505 74013
 89874579 77642565 12232014
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
5 47 2 0
0 2 0 0
3 15 1 0
6 13 0 0
6 12 1 2
13 19 0 2
17 21 5 4
12 28 4 3
68 41 11 3
206 61 9 4
427 75 23 9
944 114 74 27
2289 154 296 92
9359 267 1142 424
56750 557 1643 1059
412846 1047 2609 2039
2031161 2115 4599 4175
4596702 4666 8917 8893
5044275 9912 18119 18144
2107051 17124 29740 29952
374996 25291 40479 41053
106425 36049 51640 51504
73275 50026 62958 62742
80747 65884 75560 76156
93881 83178 90926 91108
111957 101750 108398 108368
131386 121931 127620 128077
152384 143782 147815 148545
175422 166673 170090 170679
198156 189729 194344 194549
222662 213769 217277 218590
244810 236069 239316 240521
264631 257984 261234 261867
286145 280374 281949 282664
303174 298841 300928 302119
321753 317613 318472 320089
337338 334172 335826 336587
354560 351987 352214 354770
372224 369004 369596 372489
390742 388060 390158 391003
411494 409708 408993 409708
432279 432026 430064 431773
455339 454367 453128 455260
480424 481811 480230 482254
508673 508415 507586 509806
539612 538641 538600 540559
569822 569043 568494 571181
595352 596961 595162 599606
623175 623101 621374 623871
643953 645635 643903 646205
658916 660541 657698 660828
663177 665021 664187 665420
659591 661050 658224 660435
645741 649676 644726 648574
623170 624591 622212 624093
588202 590973 588716 592030
549430 551968 549425 553122
508422 509752 506721 510320
466567 467910 465657 467583
428324 428761 428438 430615
398351 397274 396595 398607
373292 375620 374333 376391
355771 357108 354074 356065
349451 351178 349830 351662
357623 356251 354922 356576
369454 370516 367611 369904
389649 388572 388761 390995
426834 429533 426424 430281
463196 463707 462723 463292
492727 493613 492515 494983
506483 507633 505301 508254
505897 504039 502186 506747
470724 470470 469772 471677
407414 408066 407458 408419
343085 341979 341436 343352
274748 274228 273351 275076
204552 205104 204154 205366
144027 144099 144370 144346
104557 104526 104891 104642
72541 72964 72644 73410
47707 47769 47544 48240
27204 27423 27052 27492
2263 2249 2112 2140
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
