A = [
653826 637812 3667352 597338 572213 542547 541183 538785 542703 531368 557602 624478 751359 867844 976856 1098367 1177345 1215175 1215269 1194936 1165068 1162572 1165228 1145457 1151649 1372529 1372294 1362222 1546768 1278410 1272702 1253319 987891 994487 987193 983954 982309 964347 960478 967477 968918 973606 973197 984094 990177 983978 981049 981840 990275 987343 986112 983261 986069 989143 978333 974721 970024 973792 969379 953342 956718 960986 949671 949503 947755 946917 939772 932813 928983 925940 921612 932345 940817 939801 949480 948035 942712 938517 930384 923312 921900 917562 910789 904019 902381 892451 881548 867262 858040 851577 846196 839010 832554 829836 824620 818232 812952 808102 801999 794737 788964 783470 778725 774456 769152 767700 761385 756629 750602 745797 740225 734927 732533 729768 726253 727739 722522 737549 740942 741902 759713 764570 768314 766842 767507 766143 762201 759254 754737 748283 746272 740235 736386 734100 732516 728447 725712 721628 719510 715652 710617 707210 702782 700022 696790 693235 690600 687454 682437 679987 674550 671866 667918 664431 663400 658525 654996 652824 649415 644866 640076 635897 633446 629986 625803 623387 621435 617788 615310 611419 606162 603423 598960 596828 594148 591733 589891 587268 583405 579705 577411 573645 570270 567988 566024 563393 559737 558175 557199 553677 550547 547617 543779 542782 539137 536887 534204 531531 530193 526541 522687 521714 518703 515262 512342 510097 508063 506080 503218 500600 495696 492087 488681 485131 482556 480069 477264 476309 472995 472230 468080 464998 461086 460410 456412 451629 449485 444384 439109 436367 432381 428594 424065 422526 418225 414193 410239 407660 404076 400627 397063 395446 391203 388887 383553 382095 378919 376226 372615 370255 366855 363275 360463 356377 353722 350337 347949 343682 341108 338880 336651 332542 329237 325129 322979 320412 316903 315239 311668 308571 306459 303427 299190 297606 294413 291067 288431 285537 281860 279228 276598 275328 271125 269416 265139 262097 259895 257832 253315 252713 248514 246250 243876 241037 237638 235726 232500 230381 227667 225238 222737 220160 217616 215057 211511 209751 206797 205418 202531 200357 196546 194659 191847 189541 187353 184690 182890 180421 177974 176888 173275 171146 170021 166499 164870 163005 159608 157757 155682 153222 151671 149424 148054 145734 144311 141231 140015 137564 134915 134045 132265 129058 128052 125689 123258 122481 120674 118109 117275 115250 112911 111708 109897 108947 106404 105280 103649 101690 100122 98074 95931 95273 93985 92635 90563 89609 88248 86291 84855 83682 82130 80814 78820 77666 76371 75341 74444 72908 71646 70610 69000 68163 66942 65415 64037 63331 62237 61188 59386 58448 57892 56516 55201 54375 53151 52574 51349 50324 49820 48819 47475 46760 45814 45156 44314 42966 42705 41733 40312 39894 39105 38621 37628 36763 36077 35816 34920 34019 33094 32752 31930 31151 30984 29992 29415 28827 28323 27732 27012 26714 25980 25676 24740 24719 24082 23244 23260 22699 21810 21385 21058 20444 20416 19739 19619 18806 18733 18239 17762 17506 16920 16726 16275 15871 15723 15405 14765 14407 14336 13930 13631 13360 13080 12858 12442 12272 12004 11750 11543 11322 11052 10980 10538 10380 10171 10015 9691 9597 9241 8996 9057 8679 8682 8325 8243 8128 7869 7749 7668 7380 7274 7079 7037 6698 6776 6742 6523 6173 6231 5853 5761 5864 5681 5392 5318 5440 5196 5024 5038 4986 4857 4753 4568 4663 4382 4376 4175 4216 4184 4034 3919 3876 3890 3529 3584 3564 3590 3411 3417 3355 3319 3173 3220 3051 2977 2989 2887 2967 2847 2830 2643 2671 2572 2734 2510 2636 2479 2458 2371 2219 2299 2241 2180 2099 2117 2143 2088 1997 2028 1950 1938 1972 1832 1819 1799 1868 1689 1673 1734 1701 1649 1630 1632 1575 1527 1436 1458 1488 1540 1352 1455 1367 1387 1344 1259 1327 1256 1301 1247 1222 1200 1134 1154 1198 1222 1117 1028 1087 1116 1012 1018 1006 989 1040 937 1007 934 937 932 927 903 849 868 873 830 875 859 834 776 731 784 757 763 744 694 703 717 710 707 733 707 691 683 687 642 657 601 666 641 556 625 610 639 566 658 559 576 547 552 579 540 544 535 478 478 536 515 529 495 531 506 499 468 501 528 458 466 477 448 478 387 454 419 391 428 407 414 394 416 383 371 379 384 387 362 350 379 374 371 340 341 364 329 335 360 333 340 327 349 336 304 365 307 300 329 321 319 329 338 326 289 314 265 279 284 277 268 279 285 262 265 292 260 265 230 285 269 250 267 238 257 272 246 237 245 262 250 234 209 254 225 226 222 252 231 207 225 227 229 213 228 218 214 226 232 229 192 221 212 198 222 219 187 203 188 224 209 174 181 175 184 194 166 185 201 201 180 215 178 178 169 179 191 164 167 172 178 180 194 162 164 171 190 152 170 169 165 158 168 165 152 147 156 152 165 155 156 164 162 167 142 171 136 135 150 160 160 139 146 147 142 140 165 138 137 135 131 148 156 131 137 131 127 129 146 140 124 124 130 132 130 126 113 138 115 116 136 128 120 140 146 107 134 127 112 110 111 120 94 115 115 113 102 104 107 120 114 107 101 112 99 85 117 96 96 110 120 110 105 121 92 115 103 93 94 118 112 81 104 81 97 101 84 96 114 96 100 86 83 110 87 88 89 97 91 83 94 88 75 93 96 84 96 94 80 76 98 81 96 62 82 67 85 67 92 83 85 79 81 87 67 66 76 69 58 74 82 61 67 69 87 69 77 82 53 80 63 66 68 66 72 60 59 73 60 65 73 57 53 72 65 69 62 76 76 65 66 59 63 60 71 58 56 58 53 65 56 46 59 62 54 57 43 60 71 56 50 58 59 51 46 53 56 44 50 44 60 41 51 59 71 51 55 58 53 62 58 49 57 50 54 64 41 56 50 42 45 48 53 45 51 42 39 55 35 47 59 52 44 42 56 54 38 46 53 57 37 51 39 59 32 43 52 45 53 31 44 41 27 44 39 40 33 51 35 40 48 45 35 44 48 34 35 41 45 40 30 35 28 46 36 33 39 25 35 33 30 34 36 29 32 38 35 32 36 33 35 40 22 37 34 30 39 33 30 38 40 37 34 41 45 29 39 28 24 35 42 32 31 30 35 27 27 30 24 31 34 32 41 20 35 22 27 24 33 31 19 36 24 23 34 28 29 21 31 31 32 31 31 23 26 26 23 23 28 27 37 34 28 22 23 32 27 22 23 29 29 44 27 24 20 15 28 17 26 26 31 20 20 23 28 25 17 19 17 20 26 19 21 32 30 32 19 26 18 24 21 25 23 15 31 18 17 16 25 23 19 29 15 30 20 12 11 23 18 20 22 20 15 14 14 11 23 20 13 22 12 24 17 31 30 27 19 29 18 26 24 24 17 22 28 21 25 20 24 27 27 27 16 20 28 20 21 15 23 22 26 19 22 16 25 26 23 26 37 23 20 23 21 34 26 22 33 35 43 37 38 16 25 21 23 22 16 28 17 26 20 29 23 21 21 21 15 30 30 24 22 20 19 18 19 18 24 20 19 25 18 18 15 18 21 16 29 22 21 13 17 21 13 21 25 23 21 22 23 18 24 22 22 34 16 25 16 24 21 29 17 22 20 28 22 36 23 11 30 8 12 17 12 14 17 9 15 7 17 10 9 10 13 11 8 10 11 16 19 5 9 3 12 13 10 12 10 13 10 6 5 14 8 8 12 13 16 7 10 11 8 10 10 12 16 8 10 9 12 12 12 11 12 7 7 5 12 13 5 6 6 8 6 7 7 9 10 11 8 5 15 7 13 11 9 8 15 8 12 8 10 12 6 5 14 11 11 5 8 4 12 7 16 12 9 7 10 11 7 9 17 10 11 15 12 17 11 5 14 8 5 13 8 11 8 8 6 8 14 15 11 6 12 13 7 9 10 16 8 10 9 11 13 10 5 12 7 10 15 15 9 12 10 10 3 16 8 9 13 14 11 11 13 9 19 12 17 8 15 9 8 12 6 6 8 5 8 2 10 7 3 5 10 4 5 12 8 4 12 8 5 6 11 13 6 16 9 10 5 4 5 4 12 9 9 7 2 8 8 9 6 8 12 9 7 8 7 6 8 9 5 5 6 8 6 13 15 13 14 13 12 10 14 15 13 5 14 11 14 13 9 20 12 11 19 13 14 22 11 16 13 13 18 8 6 11 13 13 20 10 16 13 15 11 4 8 12 3 13 12 12 9 9 13 17 17 9 10 8 10 12 15 9 11 8 10 14 5 16 15 11 17 15 13 11 8 13 12 7 12 10 3 7 10 8 10 12 9 11 9 13 13 14 8 12 11 9 3 13 7 12 5 7 6 7 2 6 1 4 9 7 11 7 5 4 3 9 2 4 10 4 3 2 10 4 5 2 3 2 7 6 3 5 2 6 5 5 9 7 6 5 1 4 4 3 4 7 2 3 2 6 2 5 7 2 0 7 4 2 4 4 6 2 8 5 3 3 2 3 7 5 6 5 5 4 4 4 7 3 6 6 2 4 4 3 3 6 9 2 1 1 7 1 3 3 4 0 7 1 0 2 2 1 3 0 2 5 4 1 2 3 3 4 1 4 4 2 3 0 3 3 4 3 0 5 2 3 0 2 2 2 1 5 2 2 2 5 3 3 2 2 5 3 1 1 2 2 0 2 3 3 2 1 3 3 5 1 2 4 5 2 4 4 2 3 3 3 5 0 4 5 5 4 2 5 1 4 2 4 0 1 2 3 3 3 1 2 1 2 3 2 5 1 0 1 4 0 1 1 3 0 1 5 3 0 2 3 1 2 1 2 0 0 2 1 0 3 1 2 0 4 2 1 1 3 2 1 0 2 2 1 2 0 4 1 3 1 2 2 0 3 3 0 1 4 1 1 2 1 2 5 2 3 2 0 0 2 2 2 1 0 2 1 5 1 4 4 1 1 0 3 2 3 0 1 4 3 4 1 0 3 2 0 2 2 3 3 2 2 2 3 1 1 0 1 2 1 1 1 1 0 1 2 0 0 1 0 3 1 2 1 1 1 0 1 2 0 1 1 0 2 1 1 0 0 0 1 3 1 1 1 0 1 1 1 0 0 1 1 0 1 0 4 2 1 1 2 0 3 2 1 1 2 1 
];
B = [
0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
3 44 1 0
0 2 0 0
2 13 0 0
6 12 0 0
5 12 0 0
8 18 0 0
11 20 3 0
4 24 2 0
32 32 8 1
114 57 8 3
241 68 13 5
637 100 59 14
1870 145 260 75
8568 241 1050 384
53637 499 1535 991
391489 957 2438 1898
1926702 1945 4253 3869
4364541 4256 8076 8077
4780252 8913 16506 16556
1989661 15425 26951 27202
351115 22870 36765 37333
97791 32558 46795 46711
66356 45150 56958 56818
72989 59425 68475 68973
85038 74802 82314 82548
101144 91876 98160 97686
118634 110186 115339 115637
137647 129540 133365 134179
158191 150442 153492 153722
178692 170863 175178 175061
200358 192292 195581 196457
220137 212049 215529 216450
237832 231846 235301 235599
256909 251760 253324 254014
272499 268321 270257 271470
289195 285874 287061 288215
304378 301030 303150 303204
319723 317308 317639 319825
335748 332833 333807 335925
352271 349946 351960 352602
371326 369661 369371 369524
390125 389943 388147 389275
410685 410011 408853 410372
433586 434879 433581 435287
459251 458680 458739 459836
487217 485819 486830 487308
514412 513756 513657 515341
537712 539027 537990 541300
562483 562601 561477 563337
582142 583319 581788 583392
595091 596525 594596 596566
599393 600877 600538 601254
596437 597731 595469 596486
583791 587468 583158 586676
563957 564956 562868 563934
532048 534837 532755 535659
497152 499301 497028 499982
459414 461101 458275 460780
421185 421958 420728 421564
385963 386639 386547 387720
358425 357417 357142 358568
335189 337437 336318 338047
318806 320394 317588 318903
312026 313795 313037 314138
318987 317518 316895 317630
329146 329600 327520 329105
346303 345677 346079 348207
375725 375815 375451 378547
412282 412904 411919 411781
439837 440338 439823 441424
451417 452468 450844 452984
447907 446406 445294 448410
416697 415891 415782 416571
360231 360043 360490 360636
303936 302655 302884 303696
242008 241852 241355 242380
180968 181004 180652 181073
127534 127452 128015 127738
93755 93735 93968 93792
65090 65551 65191 65777
43143 43252 43087 43512
24462 24675 24293 24698
1989 1991 1844 1896
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
