A = [
656832 596051 2172485 623594 612141 576875 572952 575072 580666 567935 592119 638098 684163 745718 833636 893435 956251 1042410 1061984 1064527 1096065 1086349 1078310 1088675 1108740 1302959 1286161 1269113 1430775 1256513 1268920 1238990 1045566 1057529 1057242 1044990 1020952 1007092 1001223 982279 975912 972490 973107 966350 964901 961557 948527 944969 929305 911308 906019 903981 897161 893526 887232 884784 874082 865076 855865 849346 841354 836231 828195 822005 816688 808658 804948 798387 793230 784511 774748 768033 760395 753314 743060 738971 732535 720968 712118 708228 701224 689829 684121 677025 667080 661178 654074 646625 637655 630858 624755 617785 609355 602656 597182 590856 582530 575491 568109 561484 551361 546856 540259 536178 527418 522671 518916 511881 504513 500949 492682 485805 481854 477132 469176 464566 459898 454139 449739 443186 440145 432855 424693 420240 411830 409922 405544 400780 392247 387710 383964 380185 375225 369199 364747 359312 356663 349792 345465 339434 333761 332934 328333 325962 320820 315239 310904 306922 300378 298044 293977 292108 285745 281006 274741 271630 269092 263128 258867 254520 250790 247887 243904 240025 236537 231944 230606 227288 223194 220510 215606 213233 211462 207923 205093 200636 198827 197927 192226 187921 185781 182783 180278 176042 175717 172091 168751 166642 162666 161590 159217 158819 154302 153588 151029 148906 147426 146734 144970 141024 139507 135408 133106 131849 128522 127270 125835 123909 121189 120562 118394 114273 111909 108692 108572 106952 105114 104475 102150 101822 100306 97282 96408 92683 91841 90387 89053 88542 87068 85910 84193 82203 81219 79604 77685 77557 75395 75647 74209 72325 71111 70232 68722 68592 68477 66510 65092 64759 63365 62573 61387 60807 60176 59398 58100 57030 55382 54882 53314 53076 53030 51397 50582 50213 49287 48405 47300 46710 46445 46297 46335 45354 45410 44605 43311 42166 42064 41447 41293 41240 40421 39498 38874 38189 38540 37583 36256 36080 36295 35221 36378 35398 34503 34299 33087 32795 31716 31174 31052 30999 30202 29475 28780 29236 28445 27502 27565 27924 26746 26112 25856 26178 26039 25497 24890 24937 24906 23082 22175 21898 22625 20912 20855 20425 20431 20507 20155 19247 19014 19262 18401 18658 18979 18965 18555 17675 17715 17907 17272 17507 17478 17205 17716 17564 17965 18207 16078 15735 15927 15736 15409 15638 15335 14076 13954 13593 16256 13913 14035 13352 13626 13706 13325 15357 14460 13969 14535 13216 12586 12007 12369 11796 11556 11629 11621 12336 12035 11333 10902 10653 10264 10116 10000 9789 10800 10242 9790 9808 10318 10436 10287 10354 10565 9820 10106 9794 8239 8161 8235 8156 7925 8200 7616 7670 8000 8107 7841 7768 8014 8138 7890 8253 7928 8144 8310 7888 7993 7624 7974 7157 7002 6455 6496 6377 6539 6529 6470 6680 7275 6698 6382 5853 6118 6299 5953 5791 6085 5872 5966 5898 5250 5484 5174 5288 4976 5026 4938 5178 4820 4767 4927 5023 5175 4913 4858 4989 4845 4822 4676 4500 4920 4626 4546 4705 4772 4690 5057 4488 4694 4631 4840 4462 4555 4402 4053 3875 3866 3690 3889 3879 3852 4100 3819 3977 3958 4059 3868 3984 3822 3911 3886 3755 3816 3760 3956 3725 3781 3797 3724 3628 3759 3913 3854 3954 3720 3710 3541 3423 3478 3452 3452 3495 3306 3482 3312 3458 3229 3249 3325 3381 3153 3203 3179 3239 3236 3205 3089 3122 3078 2917 3214 3183 2978 2998 3121 3207 3014 2913 2992 3220 2909 2720 2848 3001 3019 3015 2780 2879 3028 3186 3062 3079 2980 3049 2889 3014 2828 2842 2952 2812 2571 2675 2642 2649 2464 2433 2381 2576 2572 2643 2887 2833 2667 2564 2336 2449 2360 2402 2310 2310 2271 2362 2598 2531 2372 2220 2188 2148 2197 2011 2029 2041 2150 2265 2113 2107 2078 2105 2120 2030 2079 2006 2033 1971 2109 1944 1928 1946 1849 1871 1983 2071 2075 1977 1804 1972 2008 2149 1994 2058 1850 1936 1914 1875 1962 2057 1852 1878 1904 1808 1930 1938 1979 1789 1842 1838 1902 1893 1701 1788 1773 1600 1682 1651 1489 1669 1776 1908 1993 1761 1733 1493 1421 1500 1544 1445 1542 1421 1388 1330 1307 1330 1380 1293 1233 1375 1626 1544 1484 1398 1325 1413 1336 1387 1354 1315 1446 1375 1316 1317 1392 1381 1441 1371 1566 1525 1488 1377 1277 1347 1331 1322 1375 1362 1363 1441 1491 1407 1332 1322 1400 1273 1325 1310 1291 1154 1176 1266 1236 1340 1652 1614 1480 1507 1479 1538 1609 1972 1975 1584 1542 1671 1406 1509 1527 1718 1572 1334 1498 1549 1330 1320 1367 2113 1952 2066 3007 2456 2273 1883 1565 1668 1472 1743 1563 1981 2329 1594 1827 1665 1636 1483 1615 1584 1424 1567 1144 1316 1150 1243 1094 1097 1064 1274 1204 1176 1140 1031 1076 1062 1141 1319 1217 1300 1136 1110 1880 1735 1135 1041 1047 1096 1062 1249 1153 1377 1817 1869 1428 896 1055 1157 1376 996 1186 1021 1170 1078 1011 1040 1100 1056 1027 967 1002 965 1135 1169 1567 1475 1110 1073 1069 985 1029 1071 1169 1158 1074 951 986 918 804 892 785 769 811 726 859 947 705 780 755 873 886 1032 1102 1088 1123 1081 1244 1241 1136 1088 1256 1331 1049 1049 964 1011 1091 1079 1395 1436 920 961 767 810 618 601 612 564 651 644 570 617 612 612 630 720 669 641 589 639 661 679 729 632 744 687 669 713 671 672 627 641 672 558 579 644 657 593 571 601 584 576 628 588 570 524 534 491 554 556 517 525 542 541 550 552 633 663 540 515 496 545 478 540 521 572 509 445 440 408 440 384 399 358 303 349 346 411 357 338 345 289 331 298 341 329 339 419 354 350 367 327 366 320 388 363 355 363 356 351 378 361 327 357 366 396 364 338 396 368 385 464 491 394 361 337 320 325 404 395 372 344 311 282 377 355 336 317 387 359 332 310 308 300 319 340 263 298 311 296 288 331 353 306 355 340 334 353 262 256 271 263 325 290 289 299 312 251 253 266 274 306 320 387 371 427 387 352 339 379 392 461 367 325 367 698 608 606 491 523 508 533 439 543 1063 459 429 387 409 389 342 403 379 369 358 349 325 324 291 274 333 337 383 360 399 398 411 461 511 297 243 260 290 303 258 306 290 242 292 291 264 265 235 208 202 257 316 299 355 309 235 305 233 287 266 231 281 272 274 270 300 264 296 293 304 320 303 268 342 334 452 544 444 304 414 316 369 296 255 274 277 262 336 292 336 513 352 282 245 245 253 187 198 185 190 212 256 235 305 233 313 219 249 231 235 193 180 170 195 191 187 231 195 190 235 235 193 183 193 236 229 209 190 281 268 272 253 245 202 243 337 301 288 275 234 288 310 284 276 312 367 262 359 308 357 320 337 356 355 312 332 333 387 379 408 397 285 280 282 294 298 270 258 257 247 269 214 247 256 185 197 165 197 198 233 191 253 224 279 223 188 240 175 210 203 192 150 185 219 190 179 186 185 192 221 211 201 211 197 202 123 171 165 146 131 133 191 143 142 144 147 150 104 146 129 130 137 177 130 207 142 134 124 145 149 144 172 116 128 174 130 129 161 156 146 143 163 143 168 148 142 183 154 153 166 183 131 166 128 121 147 133 123 122 127 148 141 169 197 165 175 226 186 169 167 193 166 176 185 175 190 176 151 174 171 160 152 167 156 124 145 151 128 128 129 137 132 140 155 115 118 101 108 96 114 114 114 108 100 118 100 90 72 107 98 99 96 117 87 89 102 91 124 104 86 110 115 93 121 94 115 96 96 123 110 82 92 111 79 93 83 76 82 88 73 72 58 96 103 86 117 125 100 140 131 105 123 96 101 104 102 109 98 84 115 106 107 114 107 105 128 123 112 142 121 86 129 96 105 116 105 102 103 130 97 105 114 89 115 121 107 122 84 67 88 97 96 101 102 89 89 82 95 76 76 99 79 72 85 110 90 111 78 89 85 67 86 56 65 61 91 72 84 71 66 48 54 65 54 45 56 63 56 59 74 60 62 64 82 56 68 58 51 59 56 69 69 53 71 70 76 65 73 56 87 57 76 68 79 74 82 79 67 76 76 76 78 58 67 64 58 53 58 63 94 59 73 61 49 51 88 63 57 62 60 50 58 84 84 60 63 50 54 41 44 51 55 45 54 58 50 48 45 54 73 58 64 72 60 77 67 47 45 50 57 51 46 55 46 51 38 62 43 47 47 61 51 32 41 57 58 63 65 37 67 80 66 71 57 55 54 75 58 63 77 55 72 55 80 71 55 68 63 48 67 69 54 53 63 55 60 74 63 72 63 55 52 56 63 73 62 51 57 69 51 63 56 46 53 33 60 62 57 61 46 66 51 64 50 44 49 54 46 50 52 53 70 72 73 75 90 78 105 98 84 88 97 111 94 99 90 103 120 109 132 144 178 205 154 171 152 192 158 131 177 179 218 182 185 203 217 200 171 222 213 181 191 177 171 154 254 178 152 140 244 205 367 206 172 176 180 170 596 466 902 824 795 560 478 301 400 173 36 42 27 33 40 48 40 43 58 59 56 49 34 51 53 59 53 70 53 60 53 54 55 58 58 74 78 87 199 69 97 65 72 62 60 71 67 85 65 82 68 41 63 69 57 96 96 75 86 58 64 48 59 67 69 61 96 95 117 52 72 76 72 106 75 84 78 53 74 56 72 52 30 50 45 45 21 33 63 32 43 45 30 37 46 36 43 48 47 46 50 44 39 40 38 35 50 47 35 25 23 26 32 40 38 24 39 38 18 28 40 28 38 39 35 27 34 23 39 38 40 31 33 39 37 28 32 43 43 48 41 30 36 44 39 44 45 38 33 37 40 38 39 58 41 23 19 30 39 19 32 27 28 24 19 19 23 23 28 32 24 18 35 25 42 24 20 20 35 30 38 27 19 32 26 26 24 19 36 25 25 35 28 35 29 30 36 28 29 28 31 26 20 26 28 37 26 30 37 44 23 30 32 36 28 25 26 21 24 29 28 26 43 40 37 35 41 37 36 45 16 37 33 37 27 41 39 36 58 32 33 43 43 21 31 24 34 18 29 30 32 41 24 27 22 32 23 26 19 36 27 38 32 25 29 30 31 24 33 39 26 41 43 26 21 20 32 19 18 25 32 28 28 22 32 33 16 43 29 39 25 24 29 24 38 27 39 35 24 42 30 28 25 34 24 30 16 33 27 24 43 41 37 41 33 34 25 35 41 30 29 27 22 21 
];
B = [
0 0 0
 254546 46007 208539
 258659 51281 207378
 421354 92606 328748
 248740 53904 194836
 286377 59602 226775
 340949 73746 267203
 397812 88517 309295
 412792 97206 315586
 742109 181045 561064
 350498 113104 237394
 851295 296906 554389
 386721 132646 254075
 323447 111970 211477
 240655 98044 142611
 274758 74534 200224
 140363 38594 101769
 167099 47388 119711
 116315 28325 87990
 188658 42629 146029
 141944 33898 108046
 288319 66241 222078
 232423 58452 173971
 287804 90477 197327
 297636 60354 237282
 468615 112090 356525
 229179 78145 151034
 1161926 259311 902615
 158255 57382 100873
 454008 155194 298814
 175863 59731 116132
 168038 52396 115642
 177016 66943 110073
 330615 96902 233713
 131939 50570 81369
 192975 71097 121878
 142953 49691 93262
 139678 44792 94886
 167791 63784 104007
 347450 90472 256978
 129892 50753 79139
 170996 65412 105584
 121033 49346 71687
 266629 91011 175618
 190743 77452 113291
 95251 38154 57097
 144193 56702 87491
 163460 65544 97916
 475526 105312 370214
 201117 84791 116326
 112265 45786 66479
 115682 46947 68735
 208669 86518 122151
 126053 46726 79327
 543224 131105 412119
 206648 81530 125118
 149181 58410 90771
 130601 54769 75832
 354470 100999 253471
 282224 88933 193291
 47880541 17426631 30453910
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
83 86 10 3
37 30 0 1
66 46 1 3
133 53 1 13
162 59 4 12
281 72 28 12
1276 122 102 24
5255 151 130 60
27658 256 206 120
184959 382 278 196
864205 469 381 301
1573309 783 682 405
2206652 1131 1370 551
2893530 1916 1861 850
3274521 3591 2730 1237
3323950 6948 3679 2273
2769640 12030 4982 3613
1809130 18384 6652 5543
842110 24780 8229 8802
257159 31952 8088 8567
60097 37079 11902 10824
23322 44271 15947 12655
19358 51673 14492 10628
17378 44312 19793 15234
16997 41982 18491 27053
18553 40123 12043 16911
25878 21593 10561 10717
17537 17136 10337 10671
13996 20643 11546 11374
12835 15300 14242 12182
12621 14590 11964 12546
18122 17259 12459 12854
15085 15003 13076 13124
23867 23872 13958 13861
19640 16858 14722 14879
17662 17161 15889 15892
18132 17649 16914 16697
19633 18672 18061 18404
19136 19636 18361 19669
19175 19057 18743 18741
19076 19370 18991 18929
18628 18267 18283 18656
17555 17683 17643 17449
15782 16062 15944 15796
13921 13641 13816 14008
11589 11630 11540 11637
8805 8615 8971 8986
6189 6229 6329 6410
4051 4145 4065 4109
2305 2313 2295 2350
1053 1047 1052 976
396 354 350 342
109 108 106 108
12 21 21 20
0 0 0 2
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
