A = [
882856 879135 5220222 799858 782755 746980 751593 741334 751318 735665 771240 866965 1047067 1194986 1351367 1529716 1626337 1671730 1678275 1647292 1604101 1600405 1605148 1573718 1579164 1928881 1926539 1913729 2207491 1841023 1839057 1808203 1453330 1459816 1444724 1448171 1436299 1414181 1405957 1416525 1418029 1419752 1422464 1433670 1437513 1439072 1433730 1422374 1448955 1435677 1433653 1429813 1428944 1437577 1419679 1412167 1401510 1403822 1407305 1380736 1383422 1395184 1387612 1382632 1383077 1381151 1363862 1352746 1342953 1331107 1326958 1326550 1328875 1320414 1319572 1308572 1298490 1291909 1271324 1261370 1252133 1243858 1235723 1223883 1214801 1205546 1185043 1154549 1141462 1130774 1120665 1113306 1104041 1092699 1087929 1078172 1067429 1059261 1052596 1043293 1034738 1026275 1019454 1011402 1005897 999701 990786 985121 977708 968832 961753 954020 953220 947901 942771 941646 938277 967785 974878 974452 1007297 1018344 1023068 1020793 1024057 1021420 1016979 1012960 1006494 999553 993146 987598 982203 978772 976140 971833 968102 962878 959389 950713 947608 942859 936128 933662 928037 922911 918682 914958 908512 907046 901165 895055 891498 884760 883833 877831 873707 870244 865098 860492 854409 850315 842635 837594 834164 829656 827709 821247 817600 814491 810785 805041 799892 795535 791145 786739 784144 780873 775912 772465 768139 764502 758700 756109 753492 750841 746072 742850 739294 735904 731778 728652 725064 721021 717675 712392 709941 706311 703645 701455 695243 692885 688503 683869 679087 676494 673541 670784 665971 661823 656361 650624 646589 641823 637484 635221 630799 627801 623933 620341 615997 611875 606885 601449 597707 593676 587655 581703 576448 569371 563601 559039 553604 548827 542266 539727 533710 530765 525207 518666 514761 512347 505276 500770 496247 492183 487779 484280 479230 474717 470058 465578 461130 456737 451582 447806 443745 439175 433448 429430 425860 421949 417245 412044 407381 403342 398502 395496 390630 386890 382906 379536 374323 370631 366238 362203 357526 355712 349451 346812 341126 339062 334498 330375 325288 321667 317888 315140 310119 306907 303593 299311 296570 292567 288164 285392 281619 277335 273721 271107 265716 262330 259255 256365 252451 249738 245788 243424 239737 236894 232995 230352 227248 224092 220134 216818 213208 210670 207335 204330 202603 199440 197475 193149 190129 187809 185369 182494 179509 176829 174184 173281 168598 166764 164444 161801 158990 156770 154271 152749 149670 147245 145657 144115 141125 138728 136584 135063 132120 130761 128631 126354 124512 122883 121706 118994 116923 115890 113233 112156 109210 107598 106477 104063 103537 101760 99928 98305 96271 95186 93562 92881 90990 89486 87840 86532 85790 84055 82853 81296 79732 79102 77129 76016 75290 74291 72784 71795 70635 69466 67962 67432 66369 65353 64221 63509 61911 60908 60019 59029 58791 57365 56733 55663 54475 54249 52859 52376 51377 51162 50051 48943 48403 47556 47092 46455 45497 44670 44345 43437 43529 42582 41555 41219 40568 39934 39308 38828 37946 37678 37130 36312 35736 35029 34834 34284 33664 33258 32979 32512 31557 31192 31262 30641 30185 29675 29363 28875 28245 28108 27637 27078 26594 26661 26006 25379 25100 24893 24859 24106 23889 23676 22940 22999 22360 22279 21805 21556 21407 20949 20635 20392 20082 19735 19602 19010 18716 18493 18447 18044 17762 17443 17538 17103 16839 16605 16386 15969 15859 15424 15697 15217 15084 14909 14637 14318 14145 14295 13942 13699 13622 13332 12964 12961 12750 12324 12472 12287 11975 11884 11634 11552 11259 10851 11000 10868 10758 10625 10339 10396 9980 9901 9878 9774 9533 9486 9390 9196 8858 8847 8716 8596 8287 8371 8299 8124 8019 7982 7601 7567 7735 7429 7325 7181 7142 6960 6808 6846 6836 6695 6467 6441 6343 6467 6140 5963 5912 5850 5773 5746 5603 5532 5544 5527 5324 5201 5163 5172 4949 5072 5002 4814 4733 4668 4666 4534 4492 4384 4381 4344 4203 4278 4082 4132 4073 3961 3810 3794 3818 3729 3766 3576 3481 3384 3472 3429 3317 3273 3343 3283 3285 3063 3085 3079 2933 2951 2896 2948 2758 2938 2857 2669 2669 2595 2570 2583 2551 2564 2465 2400 2392 2445 2358 2257 2249 2155 2272 2188 2118 2066 2050 1975 2049 2008 1961 1994 1947 1882 1835 1871 1771 1817 1676 1705 1754 1699 1710 1647 1634 1528 1554 1521 1576 1458 1522 1492 1427 1442 1381 1415 1353 1424 1317 1347 1245 1197 1272 1257 1176 1228 1134 1173 1146 1146 1086 1110 1139 1111 1097 1063 1017 1080 1051 1039 960 932 944 952 946 945 915 915 863 880 885 830 754 852 835 811 842 784 772 787 756 740 702 757 739 699 702 683 664 660 657 662 642 643 588 670 641 639 633 600 626 606 567 553 632 631 660 559 584 567 581 525 546 547 541 549 568 520 501 511 522 471 525 473 502 450 442 487 471 436 480 490 459 415 414 438 424 411 394 395 385 369 379 413 412 358 384 383 366 357 352 362 334 311 346 339 351 315 346 312 304 347 336 309 323 322 307 323 300 268 302 278 338 289 330 283 302 281 257 251 264 300 327 282 318 268 284 259 258 284 281 262 247 266 273 248 279 284 257 238 275 241 237 251 248 238 279 259 259 255 215 247 234 186 233 236 234 240 222 219 242 236 196 214 236 207 218 204 195 245 197 205 178 207 186 189 196 179 193 197 199 192 213 185 179 179 164 177 181 166 179 187 176 180 178 155 174 157 147 171 180 139 179 179 183 161 145 161 167 159 187 149 146 181 146 153 144 159 150 154 144 150 160 152 127 157 132 137 159 134 160 154 139 148 136 128 139 145 140 139 167 145 130 142 133 153 154 126 150 138 123 134 126 116 117 131 140 112 110 127 113 122 127 119 104 103 105 119 115 102 125 120 121 118 125 91 95 98 114 93 119 101 93 108 87 123 115 118 110 112 89 104 103 103 102 94 97 76 109 98 86 101 92 101 99 85 103 99 96 102 92 101 87 90 98 77 81 109 92 85 85 74 88 86 80 103 104 88 88 99 79 102 101 87 87 101 95 79 102 86 85 82 91 81 79 89 84 80 81 75 76 101 85 79 88 88 77 75 89 77 103 68 86 80 70 88 85 68 74 75 93 84 80 82 69 81 89 82 89 80 74 67 91 83 78 68 80 87 77 79 67 57 76 89 62 79 70 73 80 103 74 70 84 75 86 88 85 73 67 66 73 70 84 70 64 77 66 70 75 70 68 59 67 65 72 70 56 87 67 77 47 84 67 58 56 57 56 76 56 81 80 64 65 83 69 51 75 85 87 73 70 80 66 81 86 87 83 83 89 64 68 73 65 67 69 58 69 55 67 62 54 59 50 139 62 49 48 80 44 62 49 62 55 56 47 60 47 60 63 74 66 59 56 43 50 44 59 60 39 57 51 52 47 58 35 51 50 65 48 49 48 56 67 52 60 56 49 39 58 70 56 105 92 86 77 68 83 109 89 113 90 101 66 105 110 81 115 79 94 91 90 84 92 78 125 84 101 136 107 82 94 86 108 119 107 107 89 143 97 101 126 102 119 112 108 146 138 111 108 101 92 124 99 86 107 168 151 128 151 120 207 123 188 101 96 111 115 140 104 111 101 110 133 108 131 100 108 95 125 113 115 98 97 86 90 108 103 90 88 88 88 92 112 104 107 115 119 106 105 115 108 127 131 122 139 154 140 131 163 154 178 117 187 151 98 157 164 197 130 125 129 157 95 180 127 149 170 153 81 87 70 84 78 66 51 76 69 42 59 48 55 60 66 69 53 63 61 54 47 45 62 54 48 72 45 59 57 58 56 66 59 60 52 60 55 77 47 71 68 69 59 60 42 43 57 58 56 51 37 56 52 45 49 51 45 46 39 61 43 51 45 45 44 38 60 32 51 40 56 53 86 54 59 51 52 49 61 55 56 52 65 60 57 70 51 45 57 47 42 45 46 38 72 48 45 60 62 57 57 66 59 79 82 60 63 94 57 66 85 53 76 68 59 66 79 106 98 88 85 90 81 92 101 88 120 84 106 112 90 139 113 179 115 92 105 89 75 132 85 83 66 84 83 81 77 67 97 100 92 161 110 117 136 163 1945 140 152 143 174 180 141 167 232 144 181 105 177 109 137 125 139 153 107 147 116 99 237 159 186 105 125 93 116 85 105 129 105 69 107 91 90 98 80 97 73 93 68 61 67 70 96 88 75 89 58 67 83 55 56 75 65 78 87 63 85 61 68 93 80 72 54 64 73 141 118 82 84 69 79 86 68 83 80 65 66 51 65 79 58 55 70 89 66 58 55 58 61 58 56 48 54 61 43 56 58 51 46 40 41 28 23 39 36 24 29 42 36 34 35 25 37 35 30 26 36 33 44 35 40 35 36 30 32 32 36 27 23 36 17 28 30 43 29 31 46 27 32 27 35 24 41 31 29 27 35 34 40 32 26 25 32 18 28 21 27 25 19 18 19 26 21 24 21 13 28 15 18 22 20 17 18 21 19 15 24 21 24 23 26 19 24 16 30 15 12 15 23 20 9 13 12 9 15 14 11 12 29 14 19 12 19 17 15 14 14 18 15 17 17 13 13 17 15 13 10 17 22 12 14 12 19 16 9 12 14 12 17 10 10 15 13 17 12 10 7 10 13 17 17 8 12 4 13 16 16 13 5 6 5 7 8 3 5 5 8 8 4 5 9 6 3 5 11 10 6 4 5 3 7 9 11 6 7 8 5 3 7 8 5 4 6 6 5 5 15 9 3 9 9 6 7 4 5 10 6 7 3 8 6 6 12 12 7 7 2 4 4 8 8 6 3 10 11 5 6 6 3 11 7 7 4 3 5 6 9 3 9 7 6 5 1 9 6 11 9 1 7 7 8 7 4 2 9 4 7 4 6 6 4 7 8 4 6 10 6 6 8 5 6 12 2 1 5 5 8 8 2 8 5 3 5 3 12 5 4 5 7 6 7 5 5 7 11 7 9 10 11 8 10 5 7 6 11 9 4 11 13 7 11 7 10 8 12 5 4 5 9 10 9 7 6 8 4 10 9 6 6 6 4 4 9 4 10 7 6 5 11 5 10 5 7 9 5 4 9 6 4 10 10 5 5 8 8 6 7 10 11 10 4 8 4 5 5 11 7 5 4 13 4 2 5 8 5 5 6 6 5 7 5 3 7 2 4 6 5 6 6 2 4 7 2 3 3 4 2 5 7 2 5 2 3 2 3 5 3 6 4 5 4 7 5 4 5 3 15 5 
];
B = [
0 0 0
 462675 313452 149223
 1030449 753288 277161
 640368 468003 172365
 536087 394563 141524
 456457 342156 114301
 361781 274058 87723
 326280 250496 75784
 338709 263255 75454
 347047 272494 74553
 768667 612478 156189
 480081 382169 97912
 436988 350695 86293
 424993 341018 83975
 410005 330851 79154
 637096 520250 116846
 496723 403746 92977
 502818 412468 90350
 455921 373325 82596
 479373 393453 85920
 600927 496171 104756
 540450 444863 95587
 538711 445925 92786
 533859 442766 91093
 528200 438304 89896
 619816 516179 103637
 550644 457132 93512
 599071 498996 100075
 542069 452275 89794
 582806 487336 95470
 616459 515822 100637
 614019 513867 100152
 612771 513554 99217
 591164 495976 95188
 700436 588356 112080
 625009 524902 100107
 635814 532909 102905
 1217307 1026449 190858
 618744 520311 98433
 727750 612089 115661
 1131949 954488 177461
 717130 604565 112565
 1062534 896190 166344
 639342 539444 99898
 734268 619518 114750
 1100995 930524 170471
 747619 631559 116060
 1073909 906895 167014
 737870 623286 114584
 1057680 893526 164154
 743470 628743 114727
 1058729 895452 163277
 771245 652568 118677
 1051911 889308 162603
 751145 635508 115637
 1112106 941233 170873
 1003649 849432 154217
 722997 612439 110558
 1019255 863428 155827
 597305 505999 91306
 107908885 93713642 14195243
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 50 0 0
0 6 1 0
4 14 0 0
10 12 0 0
11 10 0 0
12 11 1 2
16 30 3 0
21 24 5 4
97 39 12 2
353 57 15 4
765 86 35 13
1764 96 69 29
5120 178 388 138
23664 300 1287 459
147606 569 1799 1049
985795 1104 2729 2060
3846267 2445 4915 4461
6527867 5939 11204 10746
4940449 11808 22229 22072
2024375 19848 35573 35508
802489 29902 49235 49186
257131 43651 62228 62768
107791 60865 76744 77353
100516 81313 92911 93426
116114 103207 111868 111767
137822 126659 134031 134184
162681 153404 158314 158925
191249 182907 187163 187299
222562 213844 217785 217558
255027 247597 250798 251740
290306 282168 285452 287244
324742 318328 320134 321650
359601 354374 355543 358291
392845 387293 389700 390134
422763 416280 418706 420450
450162 444818 445817 447463
470956 468063 469266 470574
491946 489231 489503 492411
511586 509199 508324 512005
529950 528607 529050 530846
551023 549922 546475 550676
571642 570794 567886 572301
596113 595149 593322 597386
622677 623801 621856 624710
656054 654502 654860 658126
689504 687938 687145 691087
725197 724905 722372 726782
758445 757568 754920 757439
785105 786233 785032 787381
807997 807470 806517 808555
817175 819787 815693 818413
811997 816923 811636 816032
794214 796496 792939 797854
765735 768921 764698 767928
723346 727049 724115 727615
671753 674587 672125 675403
618596 619827 618544 621079
563593 566790 563263 566225
513042 514937 513795 515687
468728 471392 469813 472292
438871 438646 438674 439114
414742 415749 414512 417278
397629 396840 395904 397528
395908 394317 394027 395251
405101 404849 403651 405765
424874 424108 423523 425428
452420 452087 451408 453475
496873 497143 493238 494991
532752 532116 530301 532135
556672 556694 554098 558289
561481 561513 560475 563070
550545 548384 548543 550714
503059 503477 501649 504140
420420 419588 417927 420527
336109 336236 334796 336785
258447 259792 257694 258994
187244 187090 186786 187738
128364 128668 128414 129036
95109 95480 95235 95493
68990 68856 68213 69171
47675 47823 47317 48098
30417 30712 30693 30995
2804 2760 2639 2644
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
