A = [
274343 270547 1518508 284992 282180 276032 276977 280179 284318 277502 294092 322160 362056 408278 465973 516325 543445 561436 566230 555367 537122 528733 523546 519345 524858 608274 611566 607320 675244 581485 583967 574972 483915 497098 486842 486966 482117 469865 466528 463384 466510 467284 468390 470185 468155 465352 463337 459401 454987 454016 454409 454087 457642 458126 457847 457097 455220 449284 448455 443321 443812 444802 445807 445413 447674 447731 445344 440356 439368 435417 432773 432073 432778 431878 430797 429014 427563 425210 421716 417847 415695 413137 412073 412803 411677 411839 410297 405108 401419 399459 396251 394229 392526 392536 390759 390340 389377 388387 387378 383997 383189 382090 379845 378542 378027 377501 374824 374693 371939 368729 365905 363602 362375 361596 359368 358799 357479 356210 354412 351914 349088 345957 344803 341873 341460 339899 338638 337768 335549 333279 331526 327751 326610 324897 322111 319911 319784 318438 316440 314661 312595 310015 307565 305186 303723 302485 300416 298735 298818 295589 294121 292375 289546 287577 286634 284408 283138 281184 280441 278154 276219 274307 272424 270174 268804 266101 265704 263619 262481 260956 260095 256460 255242 253807 250803 249969 246963 245680 244468 242820 240012 239171 238025 235075 233049 231461 229814 229326 227204 225822 223811 222519 220997 218747 217427 215267 214070 213382 210408 208768 207629 206960 203527 203259 201571 199674 198602 195973 194591 193527 191436 190427 188993 186854 185938 183748 181442 180475 178625 177266 175570 174658 173938 171577 170639 168821 166753 164951 163275 161946 160456 159227 158066 156854 155188 153486 152359 150139 148871 147579 145753 144091 143208 142315 140324 139093 136806 135865 134393 133211 131699 130555 128821 127511 126279 124835 123342 121624 120403 119189 117847 116580 115651 114181 113429 111589 109835 108825 107623 106840 105389 103989 102670 101906 99888 99640 97683 96813 95818 93925 93454 92623 90964 90033 89216 88054 86879 85940 84561 83580 82035 81268 80187 79232 78077 76891 76287 75569 74220 73378 72572 71740 70224 69842 68876 67509 66520 65895 65033 64270 63341 62461 61332 60634 59855 59430 58403 57071 56307 56079 54965 54321 53383 52960 51331 51598 50042 49887 49139 48737 47895 47364 46262 45328 44736 44436 43299 43496 42825 42404 40869 40488 40179 39684 39014 38411 37812 37291 36701 36231 35867 35096 34329 34471 33662 33307 32599 32242 31467 31507 30962 30213 30012 29503 29265 28625 28404 28129 27430 27209 26427 26168 25826 25065 24816 24338 24376 23714 23426 23136 22755 22425 22207 22121 21414 21109 20902 20584 20241 20071 19636 19553 19250 18698 18356 18238 18027 17625 17468 17089 17127 16643 16452 16181 15831 15569 15235 15306 14969 14694 14643 14501 14219 14042 13774 13403 12908 13112 12845 12572 12492 12501 12216 11816 11606 11730 11374 11351 11154 10832 11014 10654 10573 10158 10133 10053 9998 9764 9529 9563 9359 9336 9057 8731 8934 8592 8757 8260 8251 8158 8247 7910 7799 7814 7608 7584 7444 7185 7366 7263 7057 6938 6814 6760 6653 6513 6458 6407 6369 6231 6171 6169 5965 5933 5785 5902 5678 5648 5423 5537 5467 5339 5352 5196 5155 5105 4893 4951 5015 4884 4751 4675 4703 4502 4579 4575 4423 4527 4397 4293 4235 4184 4151 4140 4021 4115 4059 3827 3899 3979 3796 3734 3716 3782 3540 3533 3629 3519 3594 3504 3397 3388 3295 3332 3300 3298 3096 3237 3146 3127 3124 2989 2972 2921 2977 2979 2945 2907 2902 2836 2800 2846 2804 2743 2665 2636 2680 2638 2500 2609 2547 2594 2581 2588 2530 2442 2465 2398 2481 2359 2307 2389 2304 2371 2291 2302 2249 2222 2161 2225 2214 2115 2118 2116 2184 2137 2183 2162 2028 1993 1963 2010 1952 2025 1923 1986 1965 1926 1988 1916 1863 1868 1887 1893 1870 1875 1861 1865 1739 1807 1699 1784 1834 1667 1795 1822 1730 1672 1695 1660 1619 1630 1718 1697 1555 1633 1532 1586 1579 1570 1574 1553 1573 1450 1484 1439 1537 1415 1541 1478 1494 1452 1519 1381 1413 1407 1427 1422 1473 1430 1450 1318 1368 1453 1302 1329 1315 1366 1371 1389 1311 1344 1313 1385 1315 1277 1224 1288 1252 1282 1245 1267 1266 1241 1239 1227 1200 1183 1174 1233 1145 1173 1126 1129 1180 1150 1134 1125 1178 1164 1096 1108 1085 1092 1054 1120 1116 1125 1146 1059 993 1102 1082 1059 1025 1020 973 1027 1050 1012 1036 1036 993 973 993 961 975 1001 937 982 943 949 947 991 936 957 956 975 948 920 888 904 937 917 942 912 913 837 926 820 871 854 832 849 838 808 811 793 822 843 814 811 837 726 781 750 862 803 797 775 766 780 771 730 791 755 792 713 777 741 742 727 768 710 727 723 777 707 719 695 676 684 722 724 679 685 695 733 680 687 631 661 657 693 653 681 663 659 647 653 693 629 664 593 625 649 621 629 671 585 640 582 643 628 575 619 603 582 599 585 614 559 586 559 576 579 567 570 591 552 543 543 561 571 555 540 558 543 512 527 510 563 543 522 539 514 518 506 485 530 531 482 515 504 484 472 503 510 490 533 482 485 463 481 492 489 465 498 464 495 471 455 445 485 464 504 491 476 481 454 472 420 411 441 456 453 431 464 456 415 449 419 407 447 458 433 430 405 411 432 453 404 446 420 381 419 399 435 342 392 418 368 389 376 383 405 420 411 402 399 395 362 390 343 372 363 401 345 368 396 362 339 401 337 366 360 328 356 348 337 355 330 359 325 345 321 313 349 319 312 328 329 306 327 338 302 283 284 320 309 320 321 320 301 303 282 295 302 302 281 278 296 285 305 304 303 278 315 291 287 283 263 288 284 300 283 274 242 271 284 288 271 279 304 291 250 272 267 225 244 222 281 259 273 244 281 254 247 243 246 257 259 262 255 255 266 251 243 257 258 237 244 251 241 222 229 227 228 232 237 243 228 218 229 210 239 198 228 252 229 229 235 226 237 237 199 196 208 209 207 217 239 221 201 200 218 209 187 185 201 166 168 191 186 178 197 207 183 175 198 176 185 181 166 199 177 178 180 184 190 169 163 175 219 164 190 168 167 171 180 164 181 183 190 205 164 164 170 180 179 159 194 157 141 155 153 168 170 157 165 163 148 143 156 153 142 153 174 173 134 152 155 143 145 153 142 138 146 117 143 134 156 132 175 127 133 141 153 138 147 146 146 137 129 128 128 149 125 133 125 119 145 129 144 115 114 115 139 94 133 139 126 127 143 124 131 134 125 99 131 127 113 118 112 124 113 112 124 128 132 121 114 110 124 96 110 113 118 97 99 103 101 115 115 108 107 88 115 125 101 102 97 87 117 94 100 99 82 103 99 92 122 84 112 93 92 95 107 82 96 84 103 89 88 95 97 78 98 83 87 103 90 82 91 103 92 84 81 81 77 90 90 95 92 90 89 84 76 87 100 85 89 99 88 77 83 79 68 88 97 79 85 83 87 74 72 73 75 74 82 76 76 90 75 79 80 82 80 84 56 58 54 82 73 69 77 81 70 72 64 77 78 64 79 62 62 65 67 72 60 82 72 66 61 72 74 80 68 56 70 68 58 68 64 55 62 65 62 66 61 52 61 65 65 59 67 65 64 50 62 46 48 53 49 63 52 67 64 54 65 52 62 64 57 74 66 58 62 71 50 58 52 51 65 46 53 50 55 54 59 52 64 59 62 43 56 48 49 60 54 35 58 47 51 58 45 39 49 42 44 48 49 55 43 44 54 45 40 45 47 55 48 39 47 47 41 53 43 40 48 42 45 41 37 44 46 43 40 46 42 40 39 33 42 39 38 45 37 40 42 30 36 27 44 46 37 28 44 43 35 45 42 38 53 22 37 44 31 31 29 36 25 37 40 37 50 38 36 39 39 43 33 26 31 32 37 33 31 45 44 25 25 33 32 29 31 29 37 34 32 37 31 30 32 30 27 39 26 28 25 29 31 26 24 33 31 27 37 25 28 30 41 30 28 26 28 19 29 33 32 28 34 30 30 27 35 33 31 23 26 27 39 33 29 27 23 32 32 25 35 23 33 34 22 33 23 34 22 24 25 19 31 24 17 21 25 22 19 32 25 28 21 34 27 16 18 18 30 22 28 22 29 19 23 28 26 34 23 27 22 25 22 23 26 18 24 23 21 30 19 26 19 29 25 17 24 18 25 19 14 24 17 18 27 26 17 29 16 20 21 22 20 17 21 15 20 14 25 19 17 15 22 14 17 18 18 24 14 16 23 14 21 18 16 18 10 19 19 26 21 19 14 16 23 16 18 16 17 17 16 13 5 16 20 11 17 21 12 11 13 19 10 19 13 19 13 10 19 24 19 23 24 21 15 15 19 20 17 14 14 16 13 16 11 26 17 13 16 21 20 16 17 15 12 17 20 16 11 11 16 18 21 11 14 9 11 11 23 7 10 11 13 16 11 15 12 8 15 6 13 17 14 13 11 5 6 10 10 18 16 7 9 9 14 12 9 12 22 11 9 14 8 16 8 8 6 15 5 15 6 21 9 13 6 10 21 11 15 11 3 8 7 9 14 9 4 10 15 8 13 12 11 9 8 10 8 14 12 6 10 14 5 13 3 5 10 5 4 13 10 7 7 8 5 13 10 14 15 8 13 6 5 6 6 7 7 9 6 6 8 5 15 5 10 13 8 1 13 8 6 5 8 7 12 9 12 7 8 6 6 5 4 7 5 9 8 4 4 5 7 9 7 5 3 6 6 4 3 9 10 7 7 9 6 8 7 9 12 4 10 4 9 9 6 11 8 7 5 2 6 7 7 7 5 4 6 7 6 7 13 10 2 5 4 7 5 4 2 9 4 2 11 1 2 7 7 6 4 3 3 5 7 8 9 8 6 4 7 4 10 6 7 5 7 8 5 5 6 10 4 7 1 4 7 8 7 1 3 3 5 4 4 3 8 5 4 7 4 3 8 2 3 4 4 2 5 2 8 2 3 2 6 3 5 6 4 8 3 1 0 7 3 6 5 6 4 4 4 5 3 1 0 6 8 4 7 6 4 4 3 4 6 3 1 5 3 3 4 6 7 6 3 5 5 5 4 4 5 4 4 4 2 2 2 3 4 5 2 3 2 4 3 6 2 2 3 4 1 1 1 4 3 3 7 2 2 1 4 3 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
 185505 142683 42822
 253482 197272 56210
 256010 199497 56513
 205909 159736 46173
 279371 217788 61583
 210531 164062 46469
 312515 244722 67793
 425177 331076 94101
 273811 214556 59255
 271323 212695 58628
 452728 353517 99211
 325580 255874 69706
 382329 299237 83092
 288013 226754 61259
 276413 217563 58850
 476587 374685 101902
 286700 226536 60164
 457325 359760 97565
 308577 244032 64545
 463544 365828 97716
 363860 288055 75805
 425695 336492 89203
 394373 314235 80138
 440458 348769 91689
 393273 312798 80475
 459738 365466 94272
 524035 417370 106665
 314595 250735 63860
 522150 416228 105922
 339210 268839 70371
 36973348 29537494 7435854
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
0 29 1 2
0 4 1 0
0 6 1 1
3 11 2 4
0 1 1 0
5 18 5 2
13 36 8 2
69 26 42 6
718 35 105 41
4020 57 156 72
10395 81 228 147
23691 109 409 234
51854 182 810 567
122071 315 1283 985
287475 462 1973 1617
740776 864 3018 2689
1634363 1485 4668 4528
2137615 2827 7199 7107
1530162 4654 10940 10841
634421 7001 15382 15457
153425 10560 20780 20652
51353 14901 26499 26345
42106 21260 32757 33217
44539 29354 39972 39879
51278 39266 47539 47941
59786 50586 56801 57057
70179 62765 66672 66762
79948 74848 77295 76745
90458 85466 87236 87774
100819 95216 97320 97486
109298 104548 106273 106565
117487 111495 112910 114094
124449 117438 119799 119575
127001 124025 125212 124885
129197 127376 128321 128833
132632 130599 131881 131984
135038 133358 134298 134602
137021 136059 136957 136652
140017 139044 139781 139621
143897 143308 143648 143310
147673 147064 147322 147857
153173 153050 152996 153103
159639 159708 159348 159931
166277 165952 165651 166221
174274 173682 174627 174619
182005 181903 182320 182144
189492 189189 189851 189143
194747 194573 195204 195391
199445 199809 199743 199644
200555 200921 200285 201077
200346 201195 200832 200704
197131 196676 196795 197071
191393 190300 190972 191642
182992 182947 182675 183150
172878 172026 172025 171742
159382 160561 160337 159782
147327 147540 148451 147779
135299 135063 135837 136089
123120 123403 123456 123311
112667 113072 113084 113731
104313 104622 104406 103958
97712 97919 98352 98164
93549 93580 93371 93406
90482 90029 89731 89733
91019 90760 91037 90789
94864 94655 95435 95584
102104 101905 101735 102241
110191 110194 110573 110849
123815 123481 123241 123592
137790 138526 138031 138133
158488 158553 158678 158582
168335 167953 168454 167878
179069 179070 179803 179137
185838 184621 185080 184635
182109 182676 182019 182860
164971 165698 164578 164931
138235 137227 137375 137241
96910 96266 96540 96111
50213 50085 50272 50118
17671 17613 17727 17538
2765 2826 2818 2746
19 11 14 17
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
