A = [
126085 122086 664806 127722 124455 116112 116445 116745 121895 116080 123581 130176 144767 160332 182594 205671 212140 222638 227113 219335 206266 198374 194052 189937 188199 223112 224199 221759 245062 205442 206133 201077 162541 164791 165786 164059 162548 159067 156710 156186 156579 156224 156309 160232 161403 158640 162891 162803 162944 166321 165259 164403 166924 168014 166179 167086 164398 166341 163960 159096 158429 159293 158113 157356 158047 159435 158256 158489 158278 156267 158410 161642 162090 162582 164028 165922 163643 162679 159740 158406 156810 155773 154647 154115 153774 152751 151192 148553 147045 146576 144929 143565 143137 142725 141374 141407 141222 140564 139532 137949 136968 135967 134916 133784 133937 134190 133479 132707 131864 129991 129440 128242 127786 127438 126645 126772 126478 126316 125472 124148 123135 122472 122378 121312 121152 120838 120353 118997 118469 118233 116847 116640 115609 114817 114294 113866 113413 112456 113132 111907 111015 110311 110376 108100 108023 107647 107503 106394 106340 106476 105851 104443 104316 103085 102790 102095 101724 100655 100877 99718 99000 98229 97575 96816 96731 96357 95669 94400 95144 94309 93705 92637 92716 92390 91396 91346 90472 89931 89396 89041 89232 87735 87336 87361 86156 86636 85705 85206 85438 85064 84679 83901 83911 83440 82362 82631 82237 81142 81165 80670 80534 80753 80151 79594 79157 79196 78539 78383 78035 77259 76705 76350 75284 74685 74404 74077 73551 73533 72872 72651 72412 72175 71664 71129 71441 70140 69373 69452 68603 67586 67534 66770 66308 66251 65299 64535 64050 63969 63456 63296 62766 62263 61857 61022 60901 60534 60116 59602 59062 59037 58293 57929 57451 57207 56563 56262 56013 55675 55031 54813 54083 53919 53287 53107 53107 52129 52155 51727 51060 50965 50892 50372 49622 49396 48966 48636 48691 48123 47585 47552 46997 46560 46354 45959 45221 45213 44659 44069 44310 44045 43402 42720 42397 42041 41614 41809 41319 40669 40685 40145 39770 39441 39417 38700 38493 38218 37589 37565 37107 36794 36388 35908 35754 35240 34943 34779 34656 33979 33914 33441 33386 32793 32189 32110 32041 31662 31142 30819 30787 30101 29761 29400 29077 28641 28374 28233 27757 27379 26954 26815 26334 26285 25990 25991 25237 25114 24762 24355 23987 23775 23390 23118 22694 22813 22333 21882 21525 21532 20944 20772 20435 20307 19789 19726 19030 19038 18919 18531 18331 18105 17788 17327 16941 17199 16483 16330 16047 15647 15503 15259 15010 14514 14733 14146 13972 13809 13586 13451 13004 12877 12608 12495 11928 11847 11850 11302 11204 11132 10828 10560 10464 10343 10179 10021 9755 9563 9252 9295 8920 8803 8581 8342 8350 8093 7840 7816 7556 7502 7193 7191 6914 6880 6769 6461 6480 6205 6073 5970 5763 5585 5646 5511 5336 5242 5123 5071 4854 4841 4648 4431 4387 4415 4306 4296 4163 4002 3893 3849 3710 3600 3542 3351 3428 3263 3161 3151 3040 3001 2879 2748 2781 2658 2714 2502 2492 2550 2441 2317 2369 2176 2218 2174 2138 2087 2055 1879 1930 1829 1845 1706 1661 1686 1647 1566 1570 1478 1409 1439 1407 1337 1376 1307 1295 1233 1245 1131 1146 1086 1059 1050 1019 1039 993 977 980 937 858 900 883 856 845 775 755 773 740 668 710 632 634 573 617 544 639 577 571 592 525 513 527 535 494 519 420 457 414 423 451 447 369 377 393 375 337 346 346 313 331 315 299 283 288 290 303 291 275 247 275 252 242 266 242 239 218 227 228 230 214 197 222 161 187 209 175 171 166 157 149 142 156 163 164 147 159 141 149 150 113 118 140 110 152 111 122 137 128 121 94 123 115 103 106 100 104 113 90 85 95 83 79 92 76 90 70 85 89 66 75 83 79 77 73 75 59 74 63 62 64 59 65 66 72 73 72 56 67 64 48 57 53 60 57 65 58 54 59 64 57 59 55 60 51 50 51 38 61 51 52 60 52 58 47 47 50 47 55 39 44 37 45 40 42 50 46 46 45 40 45 43 41 35 34 34 40 42 37 37 34 35 38 48 40 41 44 35 43 43 34 38 38 35 26 33 42 38 27 29 28 26 36 31 32 29 24 37 34 28 36 26 29 29 29 32 30 29 37 33 23 33 28 27 27 25 23 23 31 23 25 27 28 37 25 29 25 26 34 21 22 20 30 27 29 30 19 25 21 19 27 17 22 32 29 19 18 22 25 20 25 26 21 28 18 18 25 20 17 22 18 32 18 18 21 26 24 25 21 23 21 20 27 14 20 20 22 22 18 24 21 16 16 18 24 17 21 21 10 11 18 18 14 22 18 13 20 15 20 13 14 8 17 23 16 20 14 22 17 22 17 18 17 22 14 14 10 22 9 26 26 19 17 14 8 12 16 17 24 26 14 20 20 20 16 10 15 14 12 16 13 11 23 18 15 8 18 13 13 13 13 17 12 19 11 13 14 13 12 7 10 10 10 12 13 15 18 11 14 9 14 16 14 12 17 9 9 12 16 17 18 9 10 12 12 8 10 10 12 14 14 11 17 11 11 14 6 8 12 14 8 11 18 12 12 9 13 16 12 11 9 8 11 15 12 17 7 7 10 13 6 6 11 9 10 12 17 6 15 16 10 14 13 15 14 16 9 9 7 12 10 10 8 7 4 7 7 8 5 6 7 10 17 6 8 5 11 12 7 9 8 8 11 8 7 13 7 3 7 8 8 8 10 11 6 0 6 8 4 5 7 7 11 7 10 4 6 10 7 6 4 9 7 11 5 3 4 7 4 6 5 9 5 4 5 3 8 4 4 9 4 5 9 2 9 12 2 7 4 9 7 9 8 4 6 7 4 10 8 5 8 7 6 5 6 5 4 4 8 3 3 11 2 8 8 7 5 10 3 7 6 3 5 2 5 4 2 13 9 3 4 4 2 5 3 6 5 6 5 3 7 9 6 4 3 5 7 2 3 7 3 12 8 2 7 7 4 5 3 6 6 3 7 6 7 1 5 4 2 6 8 5 5 4 1 5 6 2 4 7 8 6 3 1 7 4 4 7 5 6 0 5 4 2 4 2 1 5 4 7 1 6 3 1 7 8 3 1 6 8 4 7 3 3 3 4 2 3 1 3 10 3 4 2 7 6 7 2 5 0 7 1 4 5 7 7 3 3 1 3 2 4 5 3 3 1 7 4 3 5 3 4 6 5 2 4 1 5 4 2 1 2 3 4 1 6 4 1 2 2 5 1 2 5 3 2 1 4 3 1 4 1 3 1 2 3 3 6 0 3 2 1 3 4 2 4 5 6 1 0 5 2 1 1 3 4 2 3 3 4 1 3 2 2 3 2 1 6 3 3 2 2 3 5 2 4 5 5 2 2 7 1 0 2 1 4 2 3 2 5 1 4 2 3 5 4 3 3 2 3 1 2 1 1 1 3 4 1 7 2 4 7 2 4 4 4 3 2 3 1 7 4 5 3 3 2 0 3 1 7 2 0 4 4 3 4 2 1 5 0 2 1 2 2 2 1 1 3 1 3 0 0 2 0 2 3 2 2 2 3 1 4 3 2 3 2 1 5 2 0 2 1 1 1 2 1 2 2 0 1 1 1 3 2 2 2 1 1 0 3 1 0 3 2 2 1 1 0 2 0 0 0 3 3 1 1 2 3 0 1 1 1 0 0 3 0 4 1 2 1 1 2 1 2 0 4 3 1 2 0 2 0 0 0 0 0 2 3 1 0 1 1 2 3 2 1 1 6 4 3 2 2 2 3 5 3 3 6 2 1 3 3 9 5 0 3 6 3 6 2 9 2 5 5 4 6 2 7 6 5 2 10 6 5 5 4 3 7 5 4 4 5 8 2 9 1 2 8 9 0 9 6 5 9 3 1 1 1 1 0 1 0 1 0 1 0 1 0 0 0 2 1 1 0 1 0 1 2 2 3 1 1 0 1 2 1 3 4 1 0 2 0 2 4 1 1 2 2 1 2 0 0 2 2 1 6 2 0 1 5 2 1 0 4 2 1 2 0 1 3 4 0 3 2 1 5 1 0 4 3 1 2 3 1 0 1 0 0 2 3 2 0 0 6 2 3 4 0 1 2 2 3 0 1 1 1 0 0 1 1 0 0 0 0 0 1 2 0 2 1 2 1 2 0 1 1 0 0 4 1 1 1 1 2 0 1 0 0 0 0 1 1 0 0 0 2 0 1 1 0 0 0 0 1 0 0 0 0 0 0 1 0 2 2 0 0 2 0 0 0 0 0 0 1 1 2 0 0 2 0 1 0 1 0 2 1 0 1 0 0 0 1 1 0 1 1 0 0 0 2 0 0 0 0 2 0 0 0 0 2 0 0 0 1 1 1 0 1 1 1 1 1 0 2 0 0 0 1 0 2 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 0 0 2 0 1 0 3 0 0 0 0 1 0 0 1 0 1 0 3 1 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 2 0 1 0 1 0 0 1 1 2 0 1 0 1 0 1 1 1 0 0 1 0 0 0 0 1 0 1 2 0 0 1 0 0 1 0 0 0 1 0 0 1 0 1 1 2 0 0 1 0 1 1 2 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 0 0 2 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 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 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 
];
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
 112405 88133 24272
 65891 51951 13940
 116000 91340 24660
 107648 84132 23516
 152692 120460 32232
 69501 55042 14459
 113756 89292 24464
 176130 141381 34749
 108556 85401 23155
 75986 61013 14973
 159738 128094 31644
 136468 107717 28751
 152013 121988 30025
 64143 51069 13074
 118868 94530 24338
 153884 123614 30270
 73169 58849 14320
 151600 121504 30096
 124177 98502 25675
 148301 119197 29104
 72386 58223 14163
 148491 119195 29296
 120851 96040 24811
 148937 119663 29274
 64801 52477 12324
 159081 128027 31054
 141203 113828 27375
 60364 48655 11709
 142633 114490 28143
 99382 78364 21018
 14892582 12394511 2498071
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 15 0 0
1 1 0 0
1 1 0 0
2 0 0 0
2 4 0 0
1 3 0 0
9 6 0 0
12 4 1 1
89 5 1 0
288 6 3 0
488 8 79 10
987 14 140 37
1771 25 219 87
2953 45 277 149
5518 99 444 268
13755 230 589 474
66377 441 952 838
419097 935 1527 1437
1097904 1638 2780 2768
580374 2546 4737 4631
75171 3819 7111 7190
12872 5383 9675 9480
12671 7716 11922 12108
14897 10960 14490 14634
17256 14723 17465 17158
20272 18589 20466 20261
23683 22524 23326 23289
27207 27231 27275 27493
30590 31078 31068 30914
34868 35261 34521 34995
37572 38847 38782 38418
41953 42144 42098 41952
44647 45668 44696 45104
47801 48549 48192 48572
51140 51602 50685 51137
53050 54085 53004 53737
55783 56361 56373 56136
57870 58498 58156 58397
60630 60919 60910 60684
62849 63274 63306 62935
65227 65962 65851 65990
68048 68898 68518 68155
71038 71572 71606 71540
75150 74687 74704 74656
78102 78931 78641 78982
82489 82745 82768 82624
86205 86756 86153 85875
89942 89840 89665 90264
92671 93289 92325 93103
94080 94729 94402 94682
95042 94855 95316 94772
93868 93946 94394 94130
91298 91862 91509 91905
87904 88163 87804 88395
83085 84247 83447 83311
77518 77720 77438 77663
71257 72276 72508 71729
65806 65349 65659 65644
59809 59667 59733 60132
54849 54919 54877 54756
50847 50910 50648 51105
48298 48372 48586 48819
46727 46985 46892 47005
46329 46579 46243 46245
47517 47383 46612 47240
49293 49244 48964 49352
51811 52712 52399 51868
56476 56220 55216 55610
60568 61306 60269 60594
64216 63889 64145 64112
66169 65940 65810 65670
66095 65721 65658 65760
61843 61794 61795 61883
53973 54173 53691 54054
46237 45618 45632 45263
36735 36676 36553 36512
27469 27656 27533 27429
19426 19321 19156 19444
14422 14552 14641 14712
10179 10275 10268 10309
6907 6996 6980 6969
4431 4555 4496 4431
387 415 409 394
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
