A = [
93747 90698 538080 86184 81407 77550 77439 76862 77225 76172 79629 89051 107553 124473 141180 157735 169498 175302 175831 173603 169405 169469 170372 166950 167205 198779 197390 194720 220221 181278 182797 178470 140366 141826 140944 141492 140031 139174 139311 140397 140583 141163 141281 143350 144499 143766 143535 143300 144981 144787 143947 143673 145110 144866 142967 142488 141047 142399 141873 139217 139997 140867 139655 139127 138808 138433 136820 136211 134314 133987 134025 133364 133382 133725 133605 132579 131189 131346 128520 127518 127628 125711 125291 124517 124139 121843 120443 117462 116380 115504 115018 114006 111946 112376 111589 110384 109283 109301 108001 106577 106230 105269 104981 104536 103249 102624 101904 101183 101419 100149 99180 98418 98194 97096 97355 97904 97388 98637 99590 100050 103236 104158 104712 105420 105322 105072 104010 103737 103108 102781 102674 101999 100729 100436 101104 100154 99332 99101 98606 98595 97448 96730 96841 95923 95785 94681 95141 94491 93586 93881 92783 92558 91916 91382 91720 90864 90857 89467 89131 89163 87960 87431 87361 86685 86403 85974 85524 85040 84767 84462 83212 83403 82563 82509 82213 81598 81091 81056 80489 79930 79339 79709 79104 78459 78981 78026 77833 77272 77536 76442 76435 76311 75786 75670 75104 74764 74158 73594 74576 73602 72841 73158 72288 71628 71788 71770 71412 70845 70253 70209 69750 69400 68336 67556 68038 67261 67160 67001 67017 66542 65937 66029 64975 65362 64851 63946 63674 62929 62360 61773 61524 60917 60274 60117 58963 58741 58665 57246 57435 57023 56271 56010 55462 55405 54826 54411 53923 54125 53273 53339 53136 52158 52319 51456 50870 50632 50150 49725 49528 49583 49130 48343 47788 47428 47268 46878 46441 46478 45681 45195 45353 44702 43972 44321 43760 43260 42762 42263 42347 41603 41239 41293 40464 40612 39607 39270 39005 39076 38483 38149 37555 37101 37254 36646 36058 36012 35419 35262 34324 34306 34184 33688 33144 33228 32524 32364 31978 31958 31689 30694 30743 30480 30231 29997 29691 28989 29137 28485 28092 28237 27540 27269 27135 26843 26380 26419 25749 25356 25025 24888 24378 24565 23977 23980 23575 23068 22944 22506 22151 22094 21723 21555 21482 20943 20559 20245 20100 19815 19798 19686 19002 18865 18423 18390 18042 18165 17705 17340 17052 16585 16577 16345 16118 16110 15696 15458 15317 15343 14595 14558 14421 13959 14339 13686 13431 13133 13227 12948 12847 12547 12384 12028 11993 11779 11439 11560 11275 11011 10714 10792 10434 10250 10131 10025 9626 9452 9439 9279 9214 9004 8804 8576 8360 8489 8381 7901 7891 7661 7594 7553 7306 7167 6846 7027 6676 6596 6598 6567 6207 6176 6068 5953 5868 5689 5518 5458 5493 5264 5222 5108 5092 5044 4780 4709 4661 4389 4568 4346 4190 4064 4100 4038 4059 3852 3755 3566 3682 3637 3472 3405 3299 3292 3245 3097 3175 2947 3065 2864 2905 2737 2798 2702 2579 2584 2531 2504 2356 2301 2362 2258 2093 2250 2086 2067 2049 2019 1931 1908 1815 1838 1852 1743 1616 1662 1650 1576 1615 1541 1583 1388 1457 1466 1430 1310 1419 1321 1293 1284 1216 1202 1097 1137 1116 1037 1094 1061 1070 1040 987 969 915 931 893 908 851 857 836 807 822 789 833 768 756 678 678 751 724 673 680 685 688 627 636 605 580 563 569 590 563 555 530 542 495 553 490 504 470 469 473 442 448 427 451 445 432 409 384 368 406 388 364 396 317 323 321 361 302 357 330 341 332 324 292 318 317 251 271 266 278 259 271 250 279 248 248 270 238 270 252 251 253 234 202 226 216 234 198 245 214 214 200 174 179 204 215 172 169 172 168 171 176 187 168 171 166 170 177 175 158 132 141 164 150 145 141 119 136 148 126 129 150 138 153 152 129 125 106 132 140 114 113 118 121 92 143 132 117 108 123 125 118 119 104 108 114 97 100 108 101 103 98 94 81 82 96 107 76 99 67 78 79 102 87 83 85 87 74 75 79 86 85 70 82 78 72 75 64 83 65 80 46 73 61 49 72 55 37 58 47 51 38 54 60 45 45 66 50 61 51 55 45 45 43 54 51 45 43 33 48 42 44 54 35 39 51 52 43 46 43 61 55 38 54 69 83 75 41 45 47 64 69 49 38 39 65 43 53 63 41 59 39 50 63 45 52 55 51 50 49 51 34 47 30 38 31 37 35 39 22 31 31 22 32 26 32 39 33 38 28 26 31 20 29 19 24 50 35 26 28 37 33 27 28 30 22 37 29 38 23 32 28 25 36 29 28 33 41 39 47 52 34 42 29 30 25 33 24 33 26 28 23 44 42 35 26 38 26 29 42 23 29 28 38 28 22 48 28 24 35 27 28 37 18 21 24 31 29 29 27 34 29 22 25 28 22 34 22 36 12 26 26 27 23 19 26 27 23 19 17 13 21 17 24 19 11 19 15 24 23 13 26 24 13 14 26 21 23 32 20 13 17 22 11 20 23 33 27 23 21 22 13 24 30 18 22 18 32 27 21 21 17 10 18 26 18 11 23 13 25 10 20 16 24 21 13 15 20 18 21 20 13 17 22 22 18 25 22 15 14 15 10 9 18 23 11 18 18 23 15 10 12 15 19 17 16 17 29 20 14 11 18 19 17 20 12 10 15 9 12 9 11 9 14 6 12 15 9 13 7 8 12 17 13 15 17 11 16 16 9 8 7 13 18 10 12 15 18 15 14 10 13 10 13 11 13 19 15 12 15 8 16 21 16 18 9 14 12 11 16 16 9 12 17 12 8 7 9 4 10 13 8 15 11 11 12 6 14 14 12 9 7 8 12 12 7 7 13 9 5 11 11 6 14 10 12 8 11 13 12 12 12 5 18 9 12 11 11 7 8 8 3 5 10 8 10 14 6 13 7 9 11 13 15 13 10 9 14 17 14 15 21 14 13 13 17 7 16 14 7 9 12 7 9 7 3 11 8 7 6 8 9 11 4 11 2 8 6 7 11 9 6 1 6 8 5 3 11 3 8 6 11 5 4 6 8 13 11 6 6 8 7 4 7 2 7 8 8 9 12 5 9 10 7 4 8 9 4 14 9 5 4 7 3 6 15 4 6 4 10 4 7 7 4 8 4 0 3 4 3 6 10 8 4 6 4 3 4 5 3 7 5 2 2 3 2 9 8 7 3 11 7 2 6 6 5 7 4 6 7 6 8 6 3 3 5 9 13 4 6 6 11 11 3 1 2 10 9 5 6 6 8 6 6 7 3 9 8 6 8 5 13 6 1 3 3 7 7 6 4 8 12 9 7 5 3 7 7 7 6 3 12 9 8 6 9 10 6 8 5 3 10 8 4 7 6 3 3 5 5 0 1 2 6 9 5 11 1 4 9 8 6 5 4 5 6 12 2 3 3 2 4 2 3 4 6 6 6 6 8 9 8 11 4 3 5 5 5 2 4 4 8 1 2 2 3 12 7 1 2 5 7 2 2 0 2 5 3 2 4 3 4 6 4 6 8 2 6 7 6 0 5 3 4 5 4 1 5 2 4 4 3 2 3 2 3 1 0 0 0 7 1 3 2 1 5 2 0 3 1 2 5 5 2 4 4 8 4 7 3 3 11 7 5 8 13 9 15 8 14 6 6 11 4 2 3 3 7 1 2 4 6 1 5 4 31 2 7 6 5 4 5 5 6 4 6 5 5 9 12 0 10 8 5 1 6 9 16 5 7 3 8 5 6 12 8 10 4 3 6 6 6 15 12 13 12 12 10 12 10 16 4 11 11 13 14 9 8 13 10 18 13 7 10 15 19 16 12 11 17 11 13 14 11 10 7 9 12 13 19 5 24 11 22 19 11 13 11 8 4 11 14 6 7 10 1 14 7 8 8 7 15 7 8 10 11 10 5 5 10 7 14 11 14 10 20 13 11 9 5 8 14 10 6 4 6 4 2 2 2 3 7 7 10 19 11 12 17 9 8 10 15 13 17 10 15 16 14 12 18 26 14 12 6 20 17 8 13 14 19 9 19 18 6 17 24 16 26 8 19 11 12 11 12 10 8 12 9 6 18 11 11 8 3 3 3 4 7 4 3 3 7 5 5 7 6 5 3 2 6 6 3 2 4 1 7 15 3 4 5 4 3 6 1 3 1 6 11 3 9 2 4 3 7 1 5 4 4 5 5 8 14 5 4 3 4 6 6 4 14 6 5 10 7 5 7 14 7 6 5 5 5 6 12 5 4 8 4 5 6 3 4 7 6 4 9 3 1 4 6 3 4 1 1 5 0 2 0 1 1 1 1 2 5 1 2 5 5 2 3 6 5 2 4 1 3 3 5 1 2 2 11 1 5 2 4 1 0 3 0 6 3 2 4 3 5 1 1 0 10 2 2 6 0 3 0 0 1 1 2 0 4 2 1 0 0 1 1 1 0 1 0 0 1 1 0 1 2 1 1 1 0 1 0 1 0 1 0 1 0 0 1 1 1 0 3 0 1 0 0 0 3 0 1 1 0 1 1 0 0 1 0 1 0 0 0 0 0 1 2 2 0 1 1 1 0 0 0 2 0 0 1 0 0 1 2 1 0 0 0 2 0 1 2 0 0 1 1 1 1 1 2 0 0 1 1 0 2 4 0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 4 0 1 0 0 0 1 1 3 0 2 0 1 0 4 0 0 0 0 0 0 2 3 1 1 0 1 1 1 0 0 0 1 1 0 2 2 1 2 1 3 1 2 1 0 1 0 0 1 0 1 1 0 1 2 1 2 2 2 0 1 0 1 0 1 0 1 0 0 1 2 2 2 2 1 1 3 0 0 0 0 0 3 0 3 2 0 0 1 0 0 0 2 0 2 0 0 2 0 0 1 0 1 0 0 1 0 0 0 0 1 2 3 0 1 1 0 1 1 0 0 0 2 0 0 0 0 2 0 0 0 1 2 1 0 0 1 0 0 2 0 0 0 1 
];
B = [
0 0 0
 42184 31376 10808
 115356 88583 26773
 71164 55459 15705
 53527 41402 12125
 44303 34494 9809
 35142 27590 7552
 31885 25255 6630
 35378 28187 7191
 39104 31558 7546
 74564 60448 14116
 46235 37365 8870
 39224 31868 7356
 36888 29930 6958
 35504 29008 6496
 60780 49825 10955
 45210 37116 8094
 44979 37124 7855
 40107 33196 6911
 41689 34430 7259
 55469 46130 9339
 48376 39933 8443
 47538 39330 8208
 47281 39364 7917
 46073 38387 7686
 55912 46822 9090
 48101 39990 8111
 52324 43607 8717
 46851 39129 7722
 50226 42147 8079
 54259 45557 8702
 52967 44234 8733
 52764 44150 8614
 50040 42038 8002
 59769 50281 9488
 54066 45332 8734
 54265 45383 8882
 106315 89668 16647
 52497 44283 8214
 62461 52452 10009
 99901 84018 15883
 61585 51941 9644
 93484 78789 14695
 54368 45799 8569
 63404 53469 9935
 97522 82352 15170
 64466 54380 10086
 95617 80492 15125
 63488 53487 10001
 95022 80138 14884
 65009 54840 10169
 94968 80192 14776
 67164 56669 10495
 95531 80435 15096
 66491 56203 10288
 101844 85901 15943
 90129 75684 14445
 63436 53593 9843
 93004 78625 14379
 50718 42922 7796
 12057567 10447372 1610195
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 3 0 0
0 0 0 0
0 3 0 0
1 1 0 0
2 2 0 2
0 4 0 1
0 3 1 0
0 3 1 1
5 6 0 1
8 11 0 0
38 7 3 1
80 9 2 2
212 15 42 9
986 29 157 44
5852 67 196 128
42355 107 284 249
223994 268 529 490
565578 599 1091 1026
710557 1165 2212 2243
343184 2193 3698 3783
64494 3204 5065 5273
15628 4527 6446 6375
9455 6331 7974 8036
10372 8429 9553 9444
12147 10545 11463 11557
14261 12992 13953 13760
16788 15278 16390 16527
19530 19006 18978 18923
22362 21098 21834 21850
25467 24161 24566 24381
28887 27275 27873 27712
31466 31270 30457 30820
34148 32846 33461 33522
37432 35983 36294 36069
39717 38521 38709 38604
43466 40451 40892 40608
43125 42895 42549 43154
45156 45317 44933 45023
47581 47313 47036 47360
50312 49577 49705 49974
52595 52192 52110 52701
54932 55107 54883 54934
57582 58004 57872 58125
61053 61527 61335 61731
65632 64851 64872 65111
69138 68520 68726 69503
72551 72835 72772 73082
76595 76194 76413 76465
79720 80122 79815 79345
82142 83095 82299 83033
84516 84937 84719 84184
85189 85443 85350 85607
84924 85137 84780 85339
83636 84182 82911 83427
80021 80548 80589 80618
75704 76497 76014 76143
70910 72113 70937 71131
66376 65493 65647 65574
60362 60616 60340 60837
55113 55308 55404 55592
51579 51404 51396 51648
48267 48830 48641 48490
45640 45928 45467 45973
45085 45471 44980 45264
46168 45741 45691 46307
47498 47959 47065 47063
50194 50380 49928 50231
57765 58643 56256 55840
59480 60008 59649 59697
63327 63604 63595 63758
65164 65723 65106 65609
65030 64658 64306 65262
60900 60679 60090 60499
52990 53100 53099 52321
44447 43968 43796 43793
34973 35205 35488 34947
26199 26223 26249 26277
18796 18417 18145 18383
13353 13099 13212 13278
9230 9261 9145 9263
6024 6092 5957 6199
3383 3441 3394 3420
288 276 281 243
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
