A = [
281384 275169 1705854 252619 242271 227911 217809 216979 211437 196715 194164 191279 187579 184518 181893 178997 176598 174177 172973 171184 170016 167878 166518 166110 169190 225544 223575 226506 282545 282494 287005 289954 290928 295044 297266 294750 290880 288194 285736 282049 281273 280006 279732 279284 279609 276636 273707 270662 267669 266112 263248 262160 261920 262681 260395 258924 256495 253805 252199 248705 247436 245748 244722 243613 242853 241065 240071 238108 234887 233257 231012 229461 228143 225714 223614 223395 221510 219516 217366 215263 213467 210978 210261 208747 207635 206088 203790 203007 199956 198243 196472 194481 193428 192115 190421 190295 187627 186344 186408 183296 181809 180345 177692 177471 177367 175728 173790 173396 170672 170351 168417 166825 164882 163795 162390 161330 160660 158683 157064 156039 154865 153483 151667 149493 148208 148075 146940 145684 144955 142866 141322 140846 139737 138624 137422 135267 135090 133723 132335 131278 130015 128862 127996 127575 126220 125591 123927 123610 121558 121062 120164 118496 116909 116025 115204 114126 113474 112554 111494 111030 108878 108500 105796 105492 104425 103433 102795 102089 101082 99697 99353 97958 96398 95985 95154 94233 93173 92280 91879 90862 90057 88664 87826 87014 86910 85468 84963 83992 83423 82160 81952 81399 79790 78805 78553 77810 76122 75389 75494 74515 73426 72476 71696 70951 70208 69731 68426 67895 67316 66332 66014 65540 64657 63449 62883 62470 61894 60717 60120 59690 59074 58181 57860 56877 55777 55634 54877 54523 53623 52966 52759 51871 51294 50603 49367 49478 48659 47993 47488 46440 46576 45683 45089 44952 44386 43878 43733 43025 42617 41942 41761 40792 40458 39984 39398 38853 38573 37957 37263 37226 36497 36131 35783 35497 34876 34023 33903 33046 32833 32254 32014 31734 31126 30997 30651 29918 29657 29431 28974 28650 28310 27853 27464 27583 27259 26781 26222 26128 25727 25002 24902 24420 23894 23718 23448 23316 22912 22492 22527 22386 21752 21489 21316 21571 21131 20380 20388 19805 19898 19322 18874 18812 18842 18230 18184 17976 17588 17167 16937 16712 16817 15958 15589 15515 15226 15110 15013 14451 14299 14189 13911 13776 13578 13186 13295 12734 12673 12505 12703 12473 12484 12257 11977 12032 11671 11282 11231 11191 11045 10722 10797 11576 10385 10101 10456 10050 11427 9830 9561 9436 9263 9361 9139 8941 8714 8804 8395 8329 8086 8205 7995 7998 7855 7683 7350 7627 7429 7132 7066 7052 6891 6943 6754 6759 6916 6594 6539 6602 6516 6228 6289 6034 6372 6245 6081 5877 5532 5462 5260 5196 5262 5155 5095 5181 4957 5103 4905 4772 4498 4595 4568 4357 4382 4331 4344 4273 4195 4139 4086 3875 3821 3866 3824 3814 3583 3601 3728 3585 3544 3460 3340 3356 3411 3271 3250 3269 3155 3084 3088 2977 2875 2769 2903 2765 2713 2754 2639 2601 2657 2619 2488 2495 2457 2522 2485 2439 2389 2291 2268 2218 2156 2171 2185 2126 2213 2085 2063 2130 2045 1952 2072 1962 2006 1953 1830 1865 1802 1744 1740 1771 1712 1681 1729 1689 1628 1747 1658 1627 1583 1467 1575 1520 1551 1511 1488 1528 1448 1431 1423 1385 1358 1413 1294 1376 1310 1385 1358 1291 1344 1245 1194 1220 1230 1207 1219 1190 1179 1204 1115 1116 1149 1122 1117 1064 1122 1017 1070 997 1038 1105 1001 1063 957 1015 1026 978 1005 1004 921 1044 980 978 1006 974 980 1009 935 1080 985 925 1008 895 864 909 874 849 840 925 846 888 811 845 788 875 846 752 762 752 762 693 717 740 790 905 829 824 860 768 766 752 736 711 653 748 731 647 634 672 679 659 652 657 633 735 659 627 630 667 675 666 534 549 575 582 573 584 569 565 588 583 539 498 539 482 512 496 498 480 517 512 478 439 514 493 466 436 438 476 438 491 461 456 505 450 391 487 449 469 400 471 436 435 425 426 415 407 393 382 361 372 355 385 356 429 374 406 418 388 347 338 370 345 367 375 437 371 384 374 394 387 357 338 341 326 333 334 354 327 316 310 313 306 294 316 330 303 319 325 312 311 309 352 310 310 304 313 302 300 268 294 289 313 297 296 332 326 277 344 315 299 291 284 289 266 255 251 285 308 328 319 277 309 307 305 310 301 286 279 296 324 307 330 342 324 377 468 416 353 426 421 313 328 367 428 353 315 418 330 328 342 371 422 339 284 272 290 313 287 274 253 244 241 224 222 230 234 265 245 249 253 295 274 252 297 273 267 270 229 249 260 231 265 267 238 245 219 237 276 233 210 224 224 190 190 170 226 254 221 251 201 219 225 200 222 219 204 186 186 252 203 194 199 201 221 191 176 198 188 191 192 189 191 197 157 166 225 197 198 193 214 219 193 189 198 194 187 180 201 205 175 203 194 223 187 191 188 177 210 173 149 175 164 191 168 160 180 178 152 157 121 161 130 150 144 130 115 144 161 165 136 164 169 150 164 155 153 165 169 168 183 151 181 175 163 160 149 147 130 141 143 125 150 121 137 140 125 146 128 135 138 111 145 123 102 118 123 119 145 143 125 107 123 127 110 124 138 123 127 139 148 280 147 117 130 113 122 106 142 117 108 124 124 97 111 134 110 121 98 105 93 78 83 89 93 94 75 97 113 112 83 89 94 80 96 108 99 85 86 112 98 77 107 83 93 91 75 86 72 93 85 64 76 73 80 81 85 63 71 81 81 102 112 84 69 86 87 72 85 79 101 78 77 64 102 67 75 91 74 93 105 70 101 74 98 75 77 78 81 76 90 60 67 71 76 72 55 55 65 86 64 79 65 71 64 66 66 75 58 66 66 88 76 62 63 63 85 71 68 59 65 69 60 53 49 53 62 84 76 78 64 83 77 70 64 53 85 71 85 67 90 60 70 80 70 69 79 71 63 65 70 58 57 71 66 70 63 77 69 56 67 50 57 62 59 64 56 61 65 57 68 57 69 50 52 70 73 62 76 44 52 53 53 61 53 52 45 58 44 41 54 52 51 52 33 63 55 58 35 51 60 64 61 51 52 49 63 53 53 57 62 45 59 52 68 52 59 37 49 57 58 39 41 50 46 41 41 42 48 42 48 40 30 46 43 48 51 39 63 50 50 48 53 52 49 65 45 64 58 50 46 51 46 48 47 60 53 59 45 50 43 50 49 61 64 61 54 53 56 53 52 47 48 46 52 35 50 43 40 45 50 45 43 53 34 26 38 45 30 31 35 26 31 38 36 39 26 34 39 31 43 21 49 32 33 30 29 26 24 32 28 31 39 26 31 16 30 27 30 24 19 32 38 30 30 25 35 29 30 34 30 30 24 20 30 28 38 28 27 26 42 32 33 26 29 36 20 24 22 29 35 37 25 29 26 28 33 32 27 25 32 38 25 25 29 30 34 38 27 19 25 24 28 29 31 27 31 35 28 30 35 33 22 28 25 28 16 22 25 26 25 22 24 31 17 19 17 29 22 25 24 29 25 21 20 21 15 21 8 16 24 20 9 11 8 19 17 24 21 9 20 23 26 20 21 22 22 22 17 17 16 20 10 23 14 33 20 15 13 25 11 26 18 16 17 27 14 14 19 14 7 11 9 15 15 14 17 19 15 20 11 17 22 12 16 17 11 15 17 26 16 11 29 21 16 21 27 22 17 19 13 18 21 17 15 21 24 27 23 24 26 34 25 26 29 34 33 31 27 33 24 20 23 20 31 22 26 22 26 14 22 26 24 24 28 26 24 18 30 22 25 19 33 27 25 17 31 12 19 23 25 18 17 23 17 26 16 22 13 16 19 11 16 9 17 18 23 19 11 13 14 20 14 13 23 10 13 11 10 14 15 13 16 12 10 6 13 9 11 8 13 13 13 6 20 15 19 7 8 6 9 8 12 15 18 19 21 16 15 13 17 12 16 8 18 18 5 9 8 8 16 9 14 9 15 19 22 7 5 11 4 10 10 15 18 13 13 12 14 12 10 12 14 5 11 12 8 12 14 11 15 10 12 6 9 10 11 6 8 13 8 9 8 12 7 14 7 8 15 8 15 5 3 4 9 8 14 8 4 13 11 11 7 9 11 10 8 11 10 10 12 9 14 8 14 11 10 18 11 13 10 14 9 14 18 9 10 9 10 19 11 12 9 10 9 14 12 14 11 15 9 24 13 3 7 10 14 12 5 11 18 15 19 20 25 25 15 15 9 21 17 14 13 16 3 5 9 13 6 7 11 13 6 10 6 13 9 18 10 7 5 14 10 15 11 11 7 11 8 8 8 6 6 10 17 5 12 13 55 68 68 80 86 51 66 83 14 12 9 7 5 3 10 6 10 0 6 5 7 5 5 8 8 6 6 9 5 16 10 16 9 12 5 14 9 12 15 13 22 13 15 7 6 10 7 7 7 7 7 12 8 10 12 15 6 12 8 5 7 3 7 8 9 7 5 16 10 11 6 10 5 6 9 13 3 6 7 10 7 3 5 7 3 5 9 5 7 4 5 10 8 7 6 6 8 5 8 9 6 8 6 5 8 2 6 8 5 2 5 8 2 8 3 6 5 4 5 3 3 1 7 6 5 5 7 1 7 5 4 5 5 6 4 6 5 8 3 3 4 6 8 5 2 3 5 7 6 6 5 3 4 4 4 5 8 4 5 7 2 4 9 6 6 7 6 6 4 9 9 8 7 9 8 12 2 10 5 4 6 3 4 8 5 10 7 7 3 8 9 12 13 6 10 3 7 1 5 3 11 6 6 7 9 3 9 6 11 5 5 7 6 7 5 7 5 6 10 6 8 4 5 4 6 6 6 8 7 5 4 3 6 7 9 6 6 6 4 8 6 9 5 3 1 9 8 8 5 13 4 8 7 7 4 4 5 6 1 4 2 6 2 5 6 5 8 4 8 3 1 5 7 6 2 6 8 5 3 5 5 4 8 3 5 7 4 1 6 7 10 9 6 10 8 3 3 5 6 7 8 4 6 4 5 3 2 5 1 5 3 5 3 8 6 7 9 5 3 5 10 2 4 
];
B = [
0 0 0
 125253 26935 98318
 59513 13186 46327
 204060 49945 154115
 133446 30216 103230
 79924 17788 62136
 202121 51446 150675
 163848 39014 124834
 92850 21310 71540
 279304 70026 209278
 293187 69312 223875
 53174 12102 41072
 842304 210435 631869
 112516 28136 84380
 35991 8820 27171
 189851 56400 133451
 61564 17648 43916
 19161 5076 14085
 210597 62779 147818
 17508 4617 12891
 18214 5125 13089
 4386 1238 3148
 101 28 73
 4188 1201 2987
 312189 97294 214895
 20620 5593 15027
 26980 7820 19160
 323494 102509 220985
 19015 5798 13217
 40682 12433 28249
 516276 156351 359925
 38254 11881 26373
 67985 21218 46767
 364165 120889 243276
 242660 80249 162411
 401354 134262 267092
 741861 247872 493989
 616907 201073 415834
 373207 122543 250664
 862154 295797 566357
 349809 113988 235821
 24052 7883 16169
 794138 273932 520206
 13095 4414 8681
 22965 7510 15455
 1080600 380451 700149
 23819 8038 15781
 278739 91440 187299
 1456744 536543 920201
 275900 91340 184560
 10 6 4
 9746158 3688366 6057792
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
14 46 0 1
9 3 0 0
24 5 0 0
44 11 0 0
36 10 0 1
34 12 12 0
85 17 32 6
296 28 50 10
1046 17 50 24
3315 27 82 36
7478 40 111 60
15517 66 109 89
30470 98 195 126
61929 144 296 211
118966 212 352 298
229730 381 527 521
381425 759 842 799
456255 1497 1173 1155
379520 2433 1665 1623
221386 3278 2107 2067
88474 3994 2582 2545
21323 4124 2863 2889
5750 3827 3082 3070
4740 3745 3197 3203
4447 3799 3397 3401
4460 4106 3418 3579
4508 3643 3594 3506
4508 3741 3801 3644
4695 4095 4150 4062
4777 4317 4254 4512
5159 4623 4754 4883
5650 5077 5062 5074
5907 5532 5530 5537
6443 6160 5945 6173
6955 6914 6698 6725
7721 7551 7635 7550
8643 8369 8427 8401
9785 9526 9540 9644
10910 10832 10967 10607
12304 12022 12268 12134
13898 13758 14256 13781
16119 15992 15873 15947
18020 17944 18097 18002
20528 20717 20536 20780
23278 23719 23599 23412
26791 27098 26580 26929
30110 30191 30104 29810
33191 33420 33489 33546
37180 37312 37583 37485
41246 41016 40817 40983
44560 44846 44942 44839
48004 47793 47931 47763
51379 50831 51142 50960
54350 53800 54489 53999
57694 57461 57813 57351
60654 60200 60828 60476
64739 64895 64847 64544
69004 69200 68605 69321
73251 73650 73635 73356
76798 76914 77399 76783
81403 81728 81348 80446
82067 81453 81916 81768
79181 78600 78965 78169
68386 68023 68277 68275
50578 50817 50786 50012
27678 27758 27822 27743
11726 11997 12213 11538
6583 6631 6941 6329
5407 5298 5203 4838
4685 4655 5517 4353
3242 3315 3174 3444
2269 1939 1994 2242
174 148 143 144
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
