A = [
463371 495932 8589373 480125 417484 368288 379329 355413 362442 364416 454252 661890 951343 1215503 1590850 1913057 2028926 2157574 2207918 2088747 1915708 1789588 1684909 1707700 1846450 2020964 1963269 1853049 1804817 1476219 1400599 1243706 839319 815359 774304 752302 710899 689696 672233 651470 648230 651611 641377 640220 636589 614163 603306 588506 566770 557317 552423 540573 538114 532654 522965 512507 506507 489196 478403 473063 460988 458716 457639 447937 445030 443053 432900 428001 422924 415426 414021 413200 407171 407836 408725 403382 399571 400414 392648 390137 387158 383582 379732 381311 374459 371987 370076 364059 360908 358614 351901 349759 348145 340793 339378 337069 331615 329285 326543 319285 316030 313788 305988 305304 301734 296491 293723 291150 285454 279797 277845 268992 264636 262333 253430 251604 249587 241645 238600 233816 227215 223570 220578 212459 210188 207178 200607 197355 195292 189470 186283 183558 177215 174682 171016 166885 162671 160557 154648 152898 149455 146119 142413 140030 136562 133592 131522 128296 125683 124222 120497 118258 115681 112505 110696 108381 104837 102486 101109 98617 97115 94511 93150 91402 89066 86238 85108 83778 81873 80388 78710 77273 76217 74026 72521 70691 69632 67624 67017 65698 63760 62513 61147 59831 58815 57460 56756 54940 54227 52389 51095 51570 50228 48588 48088 47372 46082 45010 43657 43135 42342 41995 40454 39916 39126 38222 37933 36630 36109 35095 34200 33880 32865 32091 31363 31314 30654 29207 29460 28478 27918 27390 27006 26759 26394 25528 24722 24372 23770 23305 22807 22068 21777 21453 21016 20752 20298 19922 19126 19022 18576 18397 17876 17425 17606 17172 16729 16018 15830 15605 15168 14799 14530 14298 14236 13972 13702 13788 13184 12870 12728 12300 12227 11809 11566 11549 11228 11020 10714 10056 10363 10054 9852 9919 9553 9511 9197 9172 8853 8719 8462 8302 8189 8057 7793 7799 7698 7496 7278 7115 7096 7052 6898 6608 6591 6591 6406 6377 6171 5804 5823 5861 5747 5715 5612 5367 5247 5259 5162 4983 4931 4951 4796 4769 4477 4460 4599 4231 4207 4010 4097 4119 3894 3882 3823 3716 3733 3464 3370 3470 3504 3454 3666 3475 3275 3366 3218 3176 3074 2971 3149 2816 2936 2807 2867 2673 2819 2716 2560 2576 2781 2525 2521 2520 2404 2329 2389 2447 2195 2178 2314 2247 2097 2028 2009 1855 1920 1931 1907 1846 1920 1872 1849 1937 1842 1822 1732 1692 1670 1532 1632 1648 1575 1508 1412 1537 1481 1488 1444 1403 1291 1337 1352 1437 1405 1461 1460 1492 1303 1347 1108 1230 1170 1234 1205 1166 1280 1141 1084 1112 1106 1264 1097 1091 1167 1268 1325 1138 988 999 941 969 971 1028 924 997 986 890 871 868 887 888 858 887 852 873 904 871 840 841 752 856 757 770 779 813 777 783 708 660 724 713 666 696 677 737 791 727 600 657 695 805 796 696 642 695 629 608 588 647 638 710 553 705 615 645 597 632 679 626 608 671 676 672 605 634 586 609 778 624 546 624 588 668 568 595 587 573 581 557 494 689 702 794 611 596 687 619 737 607 601 806 629 819 627 552 623 623 781 652 537 787 658 857 583 650 596 587 751 609 585 705 619 805 555 525 539 640 378 399 413 431 440 460 404 437 392 393 380 424 392 451 397 353 434 372 454 420 412 468 444 447 423 362 335 405 342 397 439 382 412 412 401 362 409 368 439 459 707 603 497 446 483 391 398 432 444 441 661 598 527 445 513 397 444 559 503 449 778 612 535 509 552 398 399 511 480 393 712 492 462 394 289 289 294 278 274 295 304 279 299 270 278 270 290 262 292 291 285 329 289 278 296 258 273 240 247 258 256 257 248 298 264 257 222 241 271 257 253 260 255 276 294 218 242 242 243 243 261 234 254 292 247 219 253 278 234 291 285 224 208 261 220 261 233 230 198 256 209 239 219 220 202 207 209 207 223 235 212 208 224 208 201 201 192 212 206 203 217 235 191 245 228 162 255 217 219 225 200 199 180 208 213 181 185 176 181 198 218 218 175 197 170 211 220 175 204 184 204 172 203 190 207 178 177 159 197 170 184 214 179 225 194 225 171 195 202 179 204 155 161 184 141 179 185 177 186 158 166 198 179 184 183 149 158 162 179 160 156 186 154 160 158 166 157 159 157 173 143 118 115 152 177 173 166 163 142 159 131 156 143 152 142 155 133 143 160 151 146 124 115 167 141 139 122 149 109 128 142 114 139 120 186 140 116 143 137 135 153 135 141 150 124 120 131 157 122 135 128 155 126 128 147 140 130 128 111 136 147 113 129 104 140 140 130 107 154 123 115 116 121 120 129 124 119 104 110 100 117 112 110 124 114 122 123 130 106 126 100 133 139 128 120 102 103 131 111 116 118 119 112 111 103 102 127 117 132 89 101 77 97 100 92 111 103 104 132 104 146 115 119 119 100 96 99 101 88 99 114 105 100 76 121 82 88 89 81 104 89 123 99 105 105 98 89 103 129 92 85 97 96 92 107 111 92 90 73 91 97 86 84 92 101 90 97 89 68 88 95 84 91 99 78 82 87 89 80 83 88 107 95 92 67 100 82 90 86 77 99 68 77 60 62 82 74 82 65 81 84 83 87 65 66 84 69 83 71 76 53 63 83 90 78 94 87 60 84 84 75 81 76 82 61 93 83 101 81 87 87 86 83 85 83 87 62 79 72 73 74 77 63 64 62 90 58 66 81 67 72 63 79 60 79 61 70 81 65 65 61 78 75 58 61 63 69 57 56 66 56 79 78 66 69 51 58 41 44 46 61 64 69 57 58 59 66 51 47 36 59 63 58 66 58 67 78 56 63 79 52 62 54 53 51 63 32 54 49 54 48 50 70 77 66 65 69 61 50 59 65 46 55 65 48 55 43 56 54 48 53 54 59 76 39 46 55 37 37 34 48 46 37 39 51 46 51 43 58 50 50 44 40 68 44 45 45 38 47 46 45 42 37 46 61 44 46 46 50 43 35 52 35 38 41 37 34 55 31 30 46 29 49 45 52 42 53 44 43 27 44 33 35 43 35 41 35 38 38 38 52 49 38 45 29 42 43 37 27 32 36 36 41 50 42 46 31 43 36 52 38 48 35 47 48 46 45 40 56 45 52 42 41 37 40 37 35 46 53 40 39 46 52 46 29 27 29 45 40 38 33 37 44 36 49 33 45 45 44 49 36 35 45 18 42 47 38 37 45 46 36 48 32 43 46 40 58 36 35 44 33 47 41 47 46 43 52 34 52 38 44 38 35 59 44 43 58 38 53 41 57 45 40 25 50 36 34 33 41 47 25 36 33 35 36 29 24 39 27 20 26 23 37 30 33 26 19 19 28 30 29 22 30 21 36 23 27 31 35 22 26 24 54 30 36 39 35 40 31 30 50 22 41 28 30 24 21 37 38 25 35 27 32 26 25 76 42 43 42 21 60 35 29 35 27 76 41 50 35 36 65 29 37 49 30 27 28 29 18 31 39 38 25 14 24 21 28 25 26 27 27 21 29 18 29 25 26 20 19 25 18 26 18 22 13 20 27 31 30 20 24 36 29 18 33 32 25 22 29 19 25 35 25 18 24 24 12 24 17 18 23 9 21 28 22 20 14 26 26 33 14 34 28 20 36 15 17 19 18 16 10 13 15 24 22 25 32 28 25 33 21 9 12 19 15 22 24 17 25 27 30 22 17 21 15 16 23 19 27 26 25 20 28 20 20 21 29 22 26 22 23 21 23 24 13 26 11 11 19 18 26 13 26 21 18 19 13 18 23 17 22 7 26 21 25 12 15 11 18 17 17 25 10 16 18 13 24 25 29 16 19 18 14 14 17 16 16 19 15 21 7 20 24 23 16 26 15 22 24 14 26 15 17 31 16 13 21 20 26 20 14 20 15 15 16 20 29 17 19 9 10 24 17 12 10 8 18 23 14 12 15 24 18 18 18 18 23 26 28 17 23 19 17 20 28 15 11 13 23 35 25 25 12 28 22 22 22 10 19 8 15 16 15 19 20 17 19 15 9 11 11 11 7 9 9 18 16 13 15 14 10 15 9 9 10 11 15 16 14 16 7 13 16 18 15 13 15 8 11 12 18 10 12 20 19 19 16 27 11 15 13 20 20 19 22 25 17 10 20 17 21 22 11 13 18 21 25 22 47 21 24 15 21 6 24 11 17 13 19 23 16 18 10 17 15 13 8 10 17 15 4 20 13 7 21 27 20 18 12 18 7 13 6 8 9 11 13 6 12 16 25 13 17 19 5 14 16 13 11 15 12 18 14 6 10 16 9 8 12 10 12 7 7 3 10 7 13 13 5 11 8 24 8 11 6 7 6 7 9 19 16 12 8 6 10 9 11 4 5 10 15 6 4 8 7 8 3 12 10 8 7 6 7 14 9 5 8 9 6 7 13 11 10 12 19 5 8 6 6 6 3 12 10 7 4 14 16 10 7 9 5 2 7 13 5 8 11 8 6 4 4 7 12 10 6 9 13 11 13 15 10 8 6 8 13 45 57 28 56 43 15 20 8 17 9 31 6 9 5 9 3 8 8 15 10 9 4 2 3 7 8 8 5 15 6 11 5 4 12 5 2 7 11 13 4 10 6 9 7 4 13 6 3 5 3 6 6 12 9 4 5 9 9 10 7 5 6 3 8 3 5 1 13 4 5 8 8 9 10 8 5 5 5 9 3 5 9 13 6 7 8 6 4 2 2 6 9 6 8 6 3 3 12 2 3 8 3 3 6 8 9 4 3 5 8 4 7 8 5 4 5 5 2 6 8 2 2 4 2 2 3 2 4 9 4 3 6 3 7 2 6 3 5 4 2 8 3 8 3 10 0 4 5 4 7 2 2 4 6 5 4 3 5 7 4 2 5 2 6 5 2 8 1 0 7 5 3 4 5 10 3 2 
];
B = [
0 0 0
 55250 45020 10230
 61559 49905 11654
 69625 57955 11670
 57928 48348 9580
 55460 45473 9987
 57787 48180 9607
 71600 59324 12276
 51643 43306 8337
 76897 64575 12322
 83474 71507 11967
 55886 49716 6170
 144014 123551 20463
 52449 47662 4787
 51486 46883 4603
 41725 37381 4344
 24237 21319 2918
 35530 30894 4636
 20990 19078 1912
 22573 20238 2335
 21353 19476 1877
 25039 22739 2300
 26772 24235 2537
 40242 35078 5164
 29721 26843 2878
 45552 41437 4115
 39685 34697 4988
 82919 76058 6861
 35500 32580 2920
 120312 102433 17879
 39356 35844 3512
 29025 26570 2455
 52947 48158 4789
 58333 54688 3645
 37020 35054 1966
 59105 54193 4912
 24320 22770 1550
 28033 26272 1761
 39693 35910 3783
 47544 44473 3071
 24739 23358 1381
 45975 41833 4142
 34276 32426 1850
 22317 20908 1409
 93113 83256 9857
 30083 28291 1792
 32273 30372 1901
 56311 51761 4550
 65262 60816 4446
 62616 58624 3992
 42414 39522 2892
 33922 32196 1726
 62475 58671 3804
 38488 35985 2503
 100522 94830 5692
 51194 47445 3749
 37106 34695 2411
 44628 42608 2020
 71054 64683 6371
 108537 103204 5333
 49152826 47252261 1900565
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
15 136 26 23
3 25 3 4
6 44 4 20
27 77 2 37
19 51 14 43
32 62 75 223
6448 78 824 925
112156 110 1309 1281
1990796 145 1839 1839
5503518 153 2402 2184
5312996 207 2029 2257
5200500 262 2074 2086
6282358 415 2169 1931
6863443 645 2183 2023
4640881 959 2411 2358
2819318 1477 3314 3071
1454543 2171 4232 4264
627541 2930 5683 5628
211695 4314 7387 7415
54257 5679 9020 9201
19069 7891 10938 10934
14452 10368 12714 12886
16521 13201 15582 15584
19317 16190 17757 18570
22230 19928 21727 21358
26390 24461 24967 24928
30535 28503 29246 28985
34989 33017 33793 33751
40033 37660 38355 38659
44769 43723 43615 44019
51130 48696 48551 48932
54909 52732 53471 53217
60641 57309 57602 57819
63925 61225 61575 61568
65443 64452 64288 64127
67359 66591 66411 66586
68522 67999 68111 68223
68708 68472 68927 69285
68642 68330 68432 68212
68001 67827 67767 68383
67702 67013 67577 67253
65290 65727 65916 65865
63987 64146 64152 63894
61607 61472 61882 62007
59107 59659 59257 59438
56375 57192 57098 56610
53918 53715 53301 53586
50040 50102 49499 50026
46719 46240 46287 46037
43161 43012 43088 42989
40258 39693 39765 39602
37335 36916 37224 37549
35380 35285 35369 35901
33804 33400 33900 33836
33182 32967 32895 32867
32449 31808 32300 31919
32559 32382 31625 31989
33122 33089 33059 33765
35668 35306 34605 34643
37458 37120 37025 37470
40512 40197 39862 39967
40630 41263 39465 40127
41968 42051 43590 43402
45246 45084 45612 45282
44632 45153 45729 45965
44741 44675 44191 44388
40155 41222 40560 40619
35180 35200 36556 36526
29584 32169 29462 30053
20835 20821 20255 20444
9191 9079 9539 9972
3182 3369 1584 1523
0 0 0 1
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
