A = [
78776 68201 429459 81678 74428 78731 75732 78682 80235 73717 76218 79253 74751 76191 79364 75651 75621 78197 74575 75682 79582 74494 75571 89180 110104 184442 200359 206728 285437 302080 278112 293946 307318 285064 301400 312298 281091 293352 299951 270770 287521 297140 269766 287448 297731 268164 281250 289077 261497 275317 281881 256642 270921 282163 255172 264176 273476 248018 259769 269341 244818 254620 265151 237674 252547 261133 235072 247238 257916 229598 243958 248508 226734 238265 248949 219386 233201 241033 212611 223683 234040 209599 219815 230446 206398 217564 225806 201620 213175 218869 198103 209324 214993 193892 200949 209848 188234 199198 202266 186283 195170 198565 179673 188635 195812 175841 187884 192936 170743 179587 188385 170160 175622 182226 161970 171332 178938 161700 168030 171324 154619 163672 169088 150858 157429 163197 149661 153940 159242 143093 150323 153503 138116 143521 150277 139040 145033 148897 135429 142364 142133 128620 135283 139570 127795 135315 137203 122837 129132 132146 120188 124992 128437 117555 120856 124372 114503 120024 122033 110639 115615 117423 105837 112404 113370 102894 108814 111130 100963 104980 108831 100172 103214 104731 95682 99550 102903 93811 98048 98652 94088 95518 97827 88780 91948 94617 84671 87432 90602 81909 84831 87774 80461 83564 84706 77702 81620 82866 75759 78929 82829 73705 75401 79714 73805 75225 75977 66975 71699 73730 66760 69068 71459 64205 66646 70217 63154 64336 66214 60620 63348 64086 58010 61414 62980 57283 59757 60034 53990 57811 57495 53023 55072 56594 52613 53395 53523 49584 51097 52742 49268 49908 50468 46955 47653 48843 45477 47271 48139 44678 45427 45655 41320 43409 44987 40902 42858 43121 39233 41395 42553 38383 39804 40664 37861 38311 38308 35907 36432 37834 34947 35863 36264 32251 34398 34852 31848 33044 33570 30966 31367 32516 29949 30273 31083 28847 29217 29780 28077 28806 29648 26657 26979 28130 26375 26451 27108 24991 25521 26073 23925 24767 25646 23331 23737 24248 22185 23401 23116 21831 21870 22914 20383 21603 21812 19743 20504 20994 19048 19583 20266 18656 18838 19116 17785 18040 19118 17132 17131 17828 16608 17053 17059 15896 16096 16692 14932 15553 16187 14363 15070 15867 13794 13933 14713 13351 14046 14124 12572 13337 13975 12411 12774 13131 12407 12457 12681 11669 11825 12616 11220 11594 11714 10956 11153 11485 10312 10435 10599 9925 10057 10227 9346 9553 9744 9214 9018 9452 8956 8758 8939 8326 8511 8837 8062 8179 8477 7547 7789 7994 7420 7567 7763 6822 7260 7262 6775 6871 7141 6575 6659 6713 6146 6388 6662 5968 6177 6283 5746 5878 5935 5465 5602 5630 5230 5413 5426 5120 5183 5214 4815 5078 4912 4634 4684 4839 4526 4587 4637 4341 4403 4392 4002 4222 4221 3991 3927 4051 3771 4016 3733 3556 3650 3647 3399 3333 3594 3361 3254 3324 3095 3159 3205 3031 3020 3146 2934 2985 3022 2755 2923 2794 2582 2678 2661 2567 2590 2565 2375 2487 2443 2234 2316 2332 2113 2221 2326 2048 2152 2124 2005 2065 2074 1845 1933 1944 1858 1840 1918 1756 1750 1838 1679 1734 1645 1533 1599 1684 1527 1476 1583 1468 1482 1495 1403 1461 1478 1310 1300 1385 1277 1258 1325 1224 1215 1245 1147 1159 1200 1109 1094 1116 1113 1048 1125 1014 1002 991 944 994 994 932 921 928 920 881 903 842 860 936 820 824 794 778 768 838 729 775 818 736 702 687 682 646 698 664 601 655 651 668 642 548 564 664 551 605 598 572 555 573 584 597 513 525 493 515 463 507 511 463 454 519 454 448 490 411 438 442 414 422 426 390 410 413 369 366 374 356 389 372 344 324 368 318 321 358 334 304 320 282 313 347 303 307 310 282 297 288 266 290 290 283 268 259 281 282 266 291 249 271 249 234 232 238 239 270 229 265 234 229 224 237 209 200 230 200 226 229 230 215 193 199 252 217 220 218 179 194 191 201 217 208 194 190 168 180 184 166 190 161 179 200 162 176 184 165 181 192 155 159 171 155 144 169 157 151 158 153 151 165 159 162 141 148 144 145 128 163 149 133 146 148 141 127 126 155 172 149 138 151 150 147 121 152 135 120 160 151 136 123 132 151 121 134 117 136 130 127 143 133 127 103 123 137 110 116 123 107 128 138 125 120 125 112 120 125 103 125 136 115 124 114 139 111 123 111 127 127 143 112 109 125 116 112 104 109 102 124 117 121 127 120 109 111 130 96 120 112 106 127 106 128 107 101 104 124 97 107 114 108 102 112 114 107 120 93 108 115 99 92 122 99 90 101 105 103 85 124 98 103 105 106 114 104 108 92 105 117 103 100 105 115 100 111 96 89 136 95 121 101 104 90 107 111 105 97 96 120 109 115 103 101 105 94 106 108 101 82 116 96 105 86 96 95 103 91 100 98 100 97 120 83 89 100 91 93 102 98 104 112 95 85 106 101 105 94 109 85 95 103 113 102 108 90 99 98 101 102 105 100 122 104 87 117 108 111 94 106 98 96 91 91 98 83 106 117 101 88 102 95 110 88 110 103 93 95 79 86 96 108 94 103 86 113 83 91 102 81 108 114 91 107 98 100 105 90 88 94 111 97 106 99 100 98 106 76 89 105 109 94 94 83 97 104 99 94 95 100 93 89 85 101 86 102 80 90 102 96 75 83 86 89 100 84 108 107 97 96 90 91 84 97 87 96 112 75 100 98 108 98 90 90 87 88 96 98 92 90 96 89 108 111 90 86 102 104 90 97 97 94 90 100 75 94 104 88 109 87 101 106 71 101 97 100 108 79 95 82 101 76 76 87 103 85 101 101 81 93 79 95 86 97 109 85 101 76 98 97 97 102 98 88 90 107 74 95 100 98 80 89 88 86 98 82 77 73 91 85 91 93 87 80 100 92 98 104 94 82 91 99 95 83 92 106 77 100 104 85 82 78 81 96 82 109 83 64 104 90 95 88 98 90 102 83 91 86 89 96 93 99 77 73 97 92 87 89 87 78 93 87 83 76 83 83 96 94 89 90 111 93 83 90 83 90 87 91 105 87 78 73 86 93 89 99 70 75 94 93 84 75 88 105 81 89 82 66 86 86 86 74 88 94 97 81 93 87 85 89 84 93 96 86 75 85 78 102 88 94 83 82 78 95 81 64 101 93 69 80 89 98 79 80 99 105 83 84 70 83 78 76 75 94 93 90 86 76 81 78 74 73 73 74 91 85 80 68 88 89 92 96 82 100 74 83 83 87 89 92 86 90 70 89 74 83 82 87 79 78 94 80 82 74 79 102 84 88 81 92 80 72 84 89 69 69 80 87 84 74 74 62 92 76 87 89 80 96 61 88 101 91 88 73 88 74 85 79 77 88 64 64 98 88 75 77 85 81 74 86 86 66 71 84 69 89 88 76 72 82 83 75 80 87 83 76 62 77 77 89 85 97 82 95 66 64 80 66 64 73 74 84 80 86 88 78 74 62 77 79 67 94 71 63 65 75 69 72 73 80 101 90 76 76 79 73 71 70 78 72 66 92 75 67 85 78 67 82 74 76 93 86 79 69 80 81 85 69 80 78 80 72 71 65 79 70 71 79 81 67 76 72 68 96 63 73 64 75 72 60 85 80 57 71 84 68 70 72 72 72 65 82 81 85 77 81 77 75 79 74 77 78 72 83 79 74 83 97 69 74 74 90 74 68 68 84 79 68 72 70 63 55 70 71 79 58 79 74 59 91 66 76 76 74 76 77 72 75 66 65 96 62 71 70 62 73 66 74 80 71 75 74 65 77 75 59 85 81 78 78 57 69 82 80 81 63 67 76 69 73 73 58 65 66 67 73 74 66 67 67 72 67 71 79 55 75 57 71 71 75 81 74 71 64 62 69 69 51 72 70 69 59 69 85 60 81 80 65 83 75 79 72 79 73 69 75 63 88 81 91 59 48 69 70 70 85 65 68 72 77 70 86 67 49 66 69 80 62 62 83 71 77 78 67 67 66 77 73 66 70 66 71 70 71 73 56 69 85 56 62 66 52 69 57 76 76 68 75 63 57 79 65 84 77 72 72 72 64 83 67 66 63 78 74 71 71 81 64 57 75 61 63 79 75 57 63 63 72 53 67 72 82 47 72 75 83 66 79 59 70 82 56 70 67 77 65 74 58 68 76 59 78 54 64 77 62 63 61 80 69 63 64 67 58 66 64 87 67 88 68 82 65 59 71 58 49 62 73 64 63 63 67 63 62 51 73 52 77 71 64 50 68 78 53 62 68 61 61 65 62 53 62 60 71 64 69 63 66 63 74 60 47 59 79 54 67 53 51 65 71 64 64 62 62 70 77 72 52 66 64 73 66 60 62 60 65 50 53 75 69 74 56 71 78 74 56 65 66 74 62 78 69 65 70 77 53 80 71 73 69 68 74 61 57 80 56 61 66 55 67 59 55 59 69 68 67 59 60 63 55 62 52 56 61 68 56 54 62 77 52 56 51 69 66 69 62 44 55 61 65 83 56 61 60 62 61 78 56 62 55 67 66 47 61 64 68 58 63 71 60 62 50 71 66 60 66 64 56 51 58 69 65 54 71 53 61 66 57 69 62 61 52 78 65 59 41 63 50 46 68 50 74 52 57 53 58 59 62 50 58 59 66 76 59 57 48 64 63 58 63 76 66 51 53 63 51 64 47 47 56 72 55 61 59 56 51 67 58 76 62 55 62 56 57 65 61 60 64 59 66 53 61 67 58 75 59 57 68 44 65 46 47 61 54 53 48 41 55 56 57 60 52 51 50 63 45 76 48 55 56 57 53 65 67 52 48 58 60 63 49 50 44 42 53 56 51 41 58 67 63 71 72 53 78 40 54 66 62 60 54 48 60 64 53 59 64 40 55 52 52 54 58 64 49 53 54 63 54 58 53 70 59 66 65 45 56 66 43 56 69 53 66 59 53 61 85 57 54 43 65 63 69 67 50 50 64 60 45 58 58 48 52 65 49 56 61 52 46 58 43 47 59 
];
B = [
0 0 0
 4116 1974 2142
 2807 1230 1577
 26927 11863 15064
 943 417 526
 1546 616 930
 3107 1313 1794
 5052 2357 2695
 3627 1622 2005
 27996 12541 15455
 1787 829 958
 2341 992 1349
 3345 1454 1891
 7755 3452 4303
 8084 2098 5986
 30287 14001 16286
 3454 1277 2177
 4800 1937 2863
 7048 2606 4442
 13076 5706 7370
 4758 2098 2660
 33397 15196 18201
 5460 2262 3198
 3438 1446 1992
 9500 4319 5181
 25204 13936 11268
 5817 2369 3448
 194367 83244 111123
 935 408 527
 2998 1490 1508
 1766 844 922
 2946 1392 1554
 1353 617 736
 36055 17678 18377
 642 336 306
 2523 1281 1242
 1794 905 889
 3139 1653 1486
 727 342 385
 45554 22189 23365
 0 0 0
 0 0 0
 418 247 171
 3279 1754 1525
 474 231 243
 420 212 208
 586 288 298
 1699 921 778
 56629 27067 29562
 9 6 3
 671 351 320
 549 265 284
 722 342 380
 2665 1430 1235
 77724 36479 41245
 1224 655 569
 1024 527 497
 680 354 326
 121576 66499 55077
 20841 12181 8660
 19695851 10790007 8905844
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
7 37 0 0
1 4 0 0
0 5 0 0
2 4 0 0
2 5 0 0
3 6 37 5
176 6 88 18
1100 17 117 16
3759 20 142 43
9177 22 194 84
17185 27 237 105
31539 51 376 165
53753 134 454 207
89283 309 589 360
133008 739 767 556
193516 1652 1083 945
245261 3102 1377 1316
265606 4748 2051 1914
228569 6560 2607 2593
133422 8052 3494 3408
45661 9879 4157 4004
11105 10780 4633 4606
6241 11541 5117 5095
6362 12670 5425 5330
6514 12021 6233 6120
7549 12208 6720 6776
8134 11540 7876 7615
8564 11409 7889 7987
8777 11975 9386 8647
10069 12443 10678 10311
10708 13653 12112 11002
12624 15424 13384 13014
14659 15576 14954 15113
16408 17935 17173 15576
17316 18685 17730 17416
19658 20789 20060 19317
21584 22671 22328 21539
25534 25765 25807 25019
27613 27824 27891 27120
31556 32188 32143 31489
36368 35874 36259 36082
40234 40286 40466 39430
46809 45011 46243 45226
52514 51759 52461 51786
57740 57338 57474 56379
63492 64359 64768 63221
72931 73434 74275 72615
87399 88126 88868 87178
101186 102491 103806 99731
114288 115091 115911 112735
121924 123570 125041 121606
126738 124636 127071 123008
126003 124524 126965 121775
129581 128293 130983 125493
138023 133579 139371 130851
142601 141364 144959 137862
151358 150424 154166 146813
159954 158844 163537 155516
164696 162410 167429 160474
142465 134567 140631 138177
76074 68864 73530 70091
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
