A = [
552353 540196 3292330 564976 562446 526471 527263 536693 544966 526007 561339 602944 652286 721142 825655 899104 927980 969256 982510 941964 899685 873659 852397 840552 842508 983018 992949 981953 1084414 925874 926057 907088 747137 758140 753454 752077 743996 725477 723325 720372 722442 719019 718787 735073 739930 730418 747541 744273 744393 757825 755205 753513 763672 767400 761624 763506 753362 757050 748529 730428 728901 726864 725052 725300 723431 728254 719795 718406 718640 712172 723735 731664 739457 743516 748845 751567 747254 742962 732872 725197 721091 713703 710928 707979 706134 700978 694314 680457 673016 667807 659866 657834 656350 653320 652948 650008 644489 642770 639699 629995 626154 623648 617831 616903 614212 613804 610949 606689 602004 598738 592875 589853 586978 584651 581401 580949 580133 577351 573675 568973 565228 562883 557737 556929 553746 552776 548719 546996 542854 538440 535946 533421 527630 526159 523216 521521 517549 515469 512839 508871 507233 503511 500836 498106 494051 492739 490274 488040 485423 483357 479603 476872 473707 470699 467978 465042 462881 459776 458585 454320 452086 449464 445817 443701 441217 438251 436065 434900 431522 430673 427002 424375 421594 417908 416124 414605 412193 409524 407340 404881 403117 399954 398070 395881 394154 392906 389670 387315 386712 385157 382455 379425 378624 377038 375001 371538 371638 370070 366733 365706 362778 361628 359869 356837 355190 353188 352231 350476 348352 347413 345011 340925 339062 335780 334265 331397 327927 328332 326322 325678 323531 323083 320012 319873 316133 313899 310947 308144 306475 303028 300570 296543 294482 292958 290616 288967 286222 284278 282594 280552 278254 276230 273684 273530 269660 269227 265411 264543 261964 260242 258407 255982 255275 252964 251938 249464 247096 245907 244071 242627 239108 237508 236288 234582 232396 230685 228964 226265 224442 223017 221036 219694 217856 216352 215219 213400 210703 209688 207684 205831 203651 202159 200692 199105 197309 195828 194082 192409 191345 188195 187682 185430 183862 182463 181117 179107 177197 175465 173993 171626 170114 168830 166977 165446 163690 161962 160063 158396 156733 155839 154188 151548 150193 148820 147655 146270 144362 143031 140963 139718 138221 136764 134921 133170 131857 130140 128496 126950 125833 123489 122644 120886 119644 118188 116312 115023 113509 112186 110816 109168 107951 105753 103995 103293 101484 100547 98651 97576 96030 94452 93524 92312 90439 89216 88173 86854 85166 83758 83548 81053 80374 79075 77667 76619 74837 73604 72593 71037 70063 68906 68061 66951 65540 64599 63283 61940 60918 60083 58966 57759 56856 56076 54551 53978 53074 51891 50195 49593 49036 48325 47022 46009 45583 44169 43483 42804 41563 40481 39775 39222 38847 37506 37386 36338 35693 34717 34267 32760 32372 31828 31122 30564 29837 29084 28569 27888 27425 26766 26163 25471 25136 24383 23691 23252 22809 22260 21821 21203 20610 20229 19884 19377 18753 18278 17952 17664 17245 16935 16500 16035 15713 15195 14612 14525 14323 13770 13430 13245 12860 12795 12006 11885 11562 11309 10910 10847 10726 10369 9993 9592 9470 9256 8967 8844 8612 8288 8186 8090 7696 7608 7318 7305 7081 6787 6619 6435 6253 6230 6150 5763 5624 5628 5329 5243 5178 4860 4851 4771 4571 4470 4329 4317 4259 3972 3853 3893 3806 3690 3618 3513 3317 3301 3190 3103 3027 3054 2940 2810 2729 2786 2611 2530 2460 2463 2374 2317 2261 2254 2070 2093 2027 2017 1944 1850 1825 1747 1707 1758 1615 1657 1551 1519 1405 1440 1340 1383 1319 1362 1266 1220 1257 1167 1112 1103 1115 1110 1033 1011 1025 957 952 869 914 888 910 863 810 768 804 776 733 776 702 643 664 738 678 624 617 634 625 598 580 579 551 555 517 509 493 549 504 501 502 469 493 440 443 400 416 421 409 436 421 397 399 357 368 385 336 368 359 320 333 364 316 323 311 329 292 317 286 255 268 277 289 275 291 271 267 257 253 250 261 243 218 255 242 257 229 225 233 200 244 242 214 252 202 197 241 216 190 205 215 178 190 199 200 190 185 167 195 186 152 184 186 164 192 207 183 163 182 173 158 170 196 174 161 177 173 188 156 145 160 158 144 154 163 148 162 138 111 139 149 139 147 184 173 132 150 116 148 149 145 140 160 149 128 145 147 153 162 153 138 146 127 139 146 124 134 126 119 147 132 112 120 153 121 125 124 125 125 133 110 122 146 119 126 96 108 106 104 122 105 126 110 131 102 73 109 115 108 105 101 127 100 102 110 103 108 90 99 101 118 109 93 116 107 106 92 106 102 97 118 114 95 110 106 94 107 99 121 104 96 87 117 78 101 111 82 95 93 91 99 98 94 80 92 87 104 96 88 86 99 98 84 91 72 82 78 70 91 72 74 79 87 83 81 91 82 81 77 78 71 77 83 77 84 82 74 70 81 73 65 80 71 80 73 86 83 86 67 75 71 60 67 81 76 68 83 84 71 76 66 76 74 72 55 71 62 72 64 65 62 68 82 64 68 63 67 61 68 74 64 60 46 79 66 71 58 66 64 65 59 58 49 61 52 54 62 56 65 54 60 65 64 58 75 64 60 65 56 59 70 58 51 55 62 52 52 42 56 54 54 61 52 52 52 52 54 46 45 59 51 48 46 55 49 48 32 60 50 46 43 44 40 49 43 43 54 48 48 41 40 50 42 48 47 41 46 43 50 46 38 40 40 47 37 52 36 38 53 48 40 50 36 32 53 47 42 52 45 40 36 35 50 49 43 45 36 45 32 41 33 34 46 34 55 32 39 49 34 32 38 35 44 38 37 28 51 40 29 34 29 30 28 36 24 40 24 28 41 23 39 28 41 28 29 37 25 35 22 35 32 25 32 23 23 36 35 45 27 30 21 37 25 41 29 38 33 32 23 27 26 36 26 34 34 29 30 34 34 22 25 29 27 22 31 28 22 32 22 34 22 27 23 37 31 32 27 27 30 22 22 30 28 27 30 30 26 26 16 21 28 22 34 22 28 16 21 24 34 19 26 19 19 23 19 20 19 22 25 24 25 16 21 23 21 14 20 24 20 26 19 16 21 17 18 19 21 15 24 22 21 18 23 23 23 19 16 21 25 15 23 22 24 20 13 14 20 24 23 21 21 27 9 28 18 25 14 20 19 20 14 20 18 14 12 19 29 13 15 12 22 19 19 20 24 21 13 16 16 16 27 9 13 18 14 15 9 15 15 25 19 15 25 21 15 19 12 15 21 22 13 12 16 22 15 16 18 14 17 9 13 11 21 12 16 24 12 18 12 12 13 6 10 14 16 15 13 9 17 9 16 11 14 15 11 6 11 11 10 12 16 13 14 8 14 10 10 12 8 13 14 6 11 14 15 14 13 15 8 8 9 9 13 8 7 11 11 14 8 9 12 6 10 12 9 14 10 11 11 8 16 10 7 12 15 10 13 14 21 26 10 13 18 11 15 19 14 12 10 13 8 11 18 8 16 13 10 14 11 13 14 16 11 13 12 12 10 7 8 10 9 12 8 11 14 10 8 10 9 8 11 13 8 8 12 8 7 8 6 6 8 8 13 2 10 9 8 7 10 8 12 7 9 4 4 7 9 12 3 6 6 5 3 4 9 8 6 7 9 6 8 3 8 7 3 11 2 8 2 5 6 6 7 11 7 9 4 3 4 3 6 6 3 4 2 5 2 4 5 7 7 9 2 4 5 12 5 4 4 8 6 3 7 3 5 2 3 3 9 7 5 5 8 4 0 0 5 1 5 7 3 9 8 5 5 5 4 7 9 3 4 8 4 6 8 3 4 5 7 6 3 5 7 6 5 2 6 12 8 5 9 11 8 8 9 9 8 15 10 10 6 13 17 7 7 16 17 12 10 10 15 10 19 7 17 15 11 19 9 7 17 26 13 12 4 14 19 11 19 19 16 22 30 16 15 17 15 3 23 19 8 23 26 17 17 12 14 27 8 4 6 2 0 2 3 6 3 2 6 6 5 4 4 3 3 7 5 2 3 8 2 8 2 5 6 2 4 4 1 5 3 3 4 4 5 4 6 6 9 5 11 18 14 13 9 9 13 10 16 8 6 4 7 9 6 17 7 10 9 8 7 5 9 14 10 9 8 9 9 11 16 18 15 9 13 10 6 7 10 9 11 11 6 16 8 7 10 21 12 9 16 8 6 5 4 7 5 3 9 5 2 4 2 5 7 4 5 3 3 4 5 0 2 3 6 5 4 4 3 3 4 6 1 6 2 1 7 8 0 3 1 3 1 6 3 1 6 2 8 5 3 4 3 7 4 5 1 3 4 2 3 2 3 6 1 4 3 2 1 4 3 3 3 7 3 2 4 4 2 1 3 3 2 0 2 5 2 0 5 1 1 2 3 6 3 2 2 1 2 2 2 3 1 4 1 3 2 3 2 3 4 4 3 4 2 2 2 0 2 4 3 1 3 1 2 1 1 1 0 1 3 2 1 4 2 2 1 5 5 1 2 4 1 1 3 2 4 3 5 2 3 0 0 1 4 2 2 1 1 2 5 0 3 3 4 2 1 5 2 0 1 2 2 1 2 1 5 3 3 2 3 3 1 1 2 2 0 4 0 5 1 3 2 2 0 0 1 2 5 3 2 1 2 0 3 2 1 2 2 1 3 1 0 0 0 1 2 2 2 0 1 1 2 1 1 1 1 3 0 3 0 2 0 0 5 0 2 0 0 1 1 2 0 2 1 0 1 1 1 0 1 3 1 1 3 1 2 2 1 0 1 0 1 3 0 4 2 2 2 0 2 0 1 0 2 0 2 0 1 0 1 1 1 1 1 2 1 2 1 1 1 0 2 1 3 4 1 0 0 1 1 1 1 2 1 1 1 2 1 3 1 2 2 0 1 2 0 0 4 2 0 3 1 2 3 3 1 0 2 3 0 1 5 0 0 0 1 2 4 2 1 1 2 2 0 0 2 1 0 1 0 2 0 1 1 0 1 1 1 0 3 0 0 0 0 3 1 2 0 0 0 0 0 1 3 0 2 2 0 1 2 2 1 1 2 1 1 0 0 0 0 0 1 0 1 0 0 3 0 1 0 2 1 0 1 0 1 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
 490171 394400 95771
 281008 227090 53918
 501371 404004 97367
 467798 374559 93239
 667255 538686 128569
 300455 243518 56937
 496184 399188 96996
 764253 625360 138893
 478005 385922 92083
 330353 269566 60787
 698432 571181 127251
 599160 485611 113549
 663565 543066 120499
 282316 230285 52031
 523366 426225 97141
 675544 552665 122879
 321355 264053 57302
 665823 545599 120224
 548155 445203 102952
 653826 535998 117828
 317724 261434 56290
 648730 532276 116454
 534726 435473 99253
 656161 537897 118264
 285250 235770 49480
 698662 574349 124313
 615768 505413 110355
 266073 219531 46542
 627773 514225 113548
 439412 356217 83195
 67313602 56858214 10455388
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
6 71 0 0
0 2 0 0
2 7 0 0
8 6 0 0
4 10 0 0
13 14 0 0
54 14 0 0
214 18 1 1
814 18 2 0
2642 33 12 3
5630 46 521 66
11368 80 854 212
19033 151 1144 466
31419 275 1739 835
53589 622 2549 1577
126820 1262 3716 2664
508517 2528 5525 4498
2515348 5291 8303 8035
5031321 9998 14837 15003
2287293 14307 25126 25132
297525 20773 37330 37452
65073 29448 50235 49990
66046 40575 61465 62136
76331 56696 74770 74531
87725 75033 88471 88095
101856 95853 101890 103350
116931 116270 117659 118697
133751 135514 135151 135951
151070 154632 152565 152880
168446 172650 170539 170835
184983 189617 187262 187525
198850 204985 201878 202120
212664 218128 215703 216098
225491 230130 228508 228150
236585 242579 238457 239347
245898 252282 248406 249273
256867 260999 257427 259319
265850 269477 267401 267284
275289 278760 276761 276327
283322 288186 286431 286043
294788 298062 295609 296575
306890 310489 308410 307977
320022 321434 319896 322451
334172 337734 334852 334955
351805 352342 351096 352509
367695 368513 367828 368763
385726 386559 384457 384782
400263 401498 401621 401678
411746 414826 413167 415110
421783 423508 420897 424105
424116 424936 424210 424741
419889 421421 419828 421469
408145 410755 410065 411021
393904 396295 395196 394916
373004 375727 373861 375114
349244 350789 348848 349195
322797 323033 321918 323297
293895 295251 294479 295297
267769 268758 268749 268908
245107 245315 245379 245011
227559 228658 228458 228493
216763 217276 216194 216950
207282 208423 206441 207454
204667 205451 205269 205948
208520 209627 209405 209313
217563 217986 217106 218149
229766 230248 229919 229905
247906 248015 247845 247486
269535 268431 268538 269409
284639 284315 283969 284995
292140 292843 292230 291630
290453 292081 290929 291295
273455 272927 272339 274194
237730 237465 237435 237911
200633 200473 199017 200768
160388 159858 160187 159676
119616 118990 119869 120591
83794 83655 83966 83575
63015 62354 62409 61958
43797 43489 43749 44033
29437 29418 29442 29329
17921 17858 18001 18001
1487 1513 1522 1490
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
