A = [
672121 937398 12775133 479069 490687 481143 463434 471102 454651 441929 441448 426267 432625 423012 417739 423048 407699 407355 407938 397220 391598 391296 388176 390813 385103 386862 390968 382309 385290 380091 379641 383313 374345 371764 372328 374980 368945 366978 368134 369353 366450 367860 373330 369436 372551 375821 368592 368874 367483 363383 362211 354652 357754 356186 350716 355102 350161 351637 348801 343435 343195 339599 336817 332734 331251 327891 324325 321145 318988 313974 312774 313970 312269 309995 309756 309579 307248 305708 301433 298481 297187 294909 292443 290277 288053 286155 278246 267811 264253 260168 258886 257502 256741 254077 251367 250954 248911 247490 245860 242900 243098 240827 240090 238782 236588 236312 233544 231153 230975 230628 227884 227984 225573 224069 222390 221630 221615 219368 217764 217123 216686 213188 212761 210879 208815 206296 205027 203815 203165 200814 198708 198232 196372 194737 193990 192854 190584 188600 188023 185941 184694 182144 181337 179349 178285 177022 174412 172962 171169 170012 168547 167111 164792 163276 161607 159929 157915 156549 155941 155255 152522 150178 149582 147844 145988 144381 144019 141938 140497 138813 136603 135487 135148 134076 131969 131044 130066 128009 126778 125119 124017 122875 121849 120282 119117 118019 116499 115728 114673 112977 111527 110440 108919 107903 106186 105592 104329 103572 102503 101376 100798 98695 97807 97095 95437 95169 93640 92162 92195 90280 89134 87514 87377 85508 85045 84059 83221 82312 81676 80147 79288 77896 77530 76098 74705 73334 72847 70857 69714 68561 67519 67104 65737 64254 63849 63224 61580 61500 59951 59672 58834 57582 57392 56486 55652 54870 54005 53405 52248 51978 51443 50775 49825 49350 48195 47620 47303 46762 45590 44835 44485 43510 43775 43150 41894 41867 40706 40362 39750 39108 38688 38213 37512 37060 36554 35728 35503 35249 34314 33792 33170 32964 32575 32020 31590 30891 30936 30218 29668 29386 28810 28653 28032 27946 27311 26636 26366 25799 25664 25382 25161 24497 24075 23851 23392 22976 22690 22520 22153 21886 21025 21139 20907 20464 20032 19985 19468 19335 18822 18911 18314 18121 17715 17509 17413 17079 16674 16580 16154 16030 15815 15621 15386 15218 14832 14620 14565 14233 14099 13609 13246 13373 13126 12971 12751 12452 12211 12083 11975 11916 11443 11472 11009 11060 10790 10647 10469 10434 10324 9964 9898 9556 9634 9589 9338 8942 8902 8938 8660 8514 8318 8290 8168 8174 7927 7843 7731 7493 7534 7547 7199 7144 7097 6885 6877 6521 6411 6510 6388 6341 6132 6053 5961 5881 5763 5595 5603 5466 5522 5417 5198 5219 5086 5123 5031 4854 4784 4823 4676 4512 4379 4321 4277 4257 4230 4025 4114 3894 3810 3872 3809 3702 3678 3637 3548 3403 3582 3248 3401 3340 3225 3228 3119 3122 3113 3018 2976 2960 2914 2737 2766 2784 2732 2691 2647 2631 2560 2432 2534 2445 2481 2308 2360 2225 2233 2180 2218 2135 2155 2131 2038 2098 2024 1956 1886 1919 1955 1854 1818 1865 1774 1726 1694 1650 1740 1626 1615 1607 1588 1616 1510 1467 1459 1393 1427 1450 1393 1358 1352 1362 1369 1256 1249 1240 1273 1205 1222 1186 1228 1187 1170 1113 1099 1138 1072 1059 1134 1015 1024 998 971 964 998 965 909 908 836 887 838 888 866 772 870 843 826 793 849 809 797 757 708 733 779 721 725 697 716 701 673 632 669 655 685 701 676 628 662 632 664 580 581 627 590 600 639 564 572 534 569 563 526 520 579 546 512 514 535 528 465 536 544 497 458 460 456 466 469 470 449 473 490 430 451 441 423 468 425 403 425 410 421 412 369 414 373 399 382 379 368 378 378 375 376 364 383 343 319 359 333 324 304 378 382 331 305 315 400 336 321 286 308 333 317 302 293 302 352 291 284 303 303 309 308 277 250 298 298 266 287 267 329 260 265 275 281 250 240 272 284 249 285 248 268 291 280 265 236 258 267 277 261 274 268 278 291 288 280 253 241 254 231 273 280 252 234 247 233 248 217 274 274 259 236 291 286 240 238 230 220 270 226 267 235 233 225 234 240 228 244 228 228 192 230 202 234 248 204 206 198 225 195 177 191 228 187 168 211 186 175 173 194 176 188 182 173 191 195 172 204 205 199 192 194 180 208 202 202 175 177 188 171 189 192 189 198 207 162 191 180 169 175 192 209 193 204 200 205 202 220 200 198 176 202 193 179 213 185 189 199 175 175 185 195 165 167 153 169 163 170 160 145 158 151 170 167 179 176 160 150 146 139 151 150 156 158 143 170 151 138 125 142 147 169 151 147 138 130 126 136 156 131 143 159 141 152 126 134 123 142 141 120 132 126 145 109 133 137 145 136 130 134 117 152 146 130 140 135 143 134 122 143 157 125 124 131 150 144 142 138 136 147 126 130 141 150 143 132 145 115 139 144 134 147 148 138 121 157 150 126 133 127 135 132 130 124 111 135 136 132 112 112 110 112 119 136 140 110 119 113 113 120 112 125 120 136 117 111 127 113 107 135 101 105 108 111 116 104 111 125 112 119 123 110 109 141 121 95 115 105 127 108 117 101 109 127 112 135 116 120 100 112 131 137 100 138 127 100 104 111 138 106 115 125 110 115 119 122 122 123 101 114 109 124 112 93 126 85 111 119 101 106 97 118 104 95 90 142 131 105 128 116 138 116 130 117 122 100 109 115 108 113 119 98 93 104 108 83 87 96 97 89 100 86 97 102 122 76 95 93 98 82 75 81 95 99 104 107 94 99 82 99 108 97 101 114 100 79 105 89 101 90 96 85 78 81 88 66 90 77 90 76 82 75 76 85 92 76 79 93 86 82 78 66 87 91 66 86 63 70 56 65 60 69 73 70 52 46 67 82 81 58 59 65 67 78 69 51 58 55 56 68 65 59 59 78 70 75 76 91 91 98 110 84 89 92 78 96 78 75 81 88 70 72 58 73 74 93 95 82 88 93 74 68 71 69 68 89 67 61 64 65 62 62 69 51 53 49 46 63 51 57 68 61 54 67 78 82 125 151 151 151 197 201 192 207 226 184 168 227 157 161 117 163 168 135 168 167 170 138 168 157 194 161 156 191 204 184 253 163 143 170 199 215 181 168 180 159 161 135 150 152 136 154 153 137 146 102 99 117 116 98 76 49 71 253 47 53 44 37 137 45 40 42 38 58 56 47 57 51 49 40 48 62 36 55 50 75 74 81 75 72 73 99 84 75 88 85 91 112 111 111 118 119 110 118 136 159 122 129 161 154 190 197 209 202 191 224 244 248 260 257 210 247 210 258 273 223 260 258 297 194 184 138 116 100 90 53 57 53 42 35 41 31 33 43 38 38 35 38 53 54 53 36 46 54 34 50 55 49 45 36 34 44 49 50 47 50 44 42 50 36 49 46 50 64 38 47 43 51 48 44 46 36 37 53 46 37 42 50 59 49 37 48 36 53 38 34 29 32 28 34 39 33 56 40 37 40 37 47 54 39 53 52 35 32 26 30 49 49 42 35 45 48 39 35 38 41 30 38 37 46 31 45 33 39 42 40 33 25 30 33 26 23 33 46 28 32 35 35 33 35 34 36 47 42 41 30 45 29 43 47 41 33 33 37 39 36 28 20 37 36 36 31 35 38 46 51 27 41 40 32 34 38 34 39 34 44 46 16 34 27 18 45 79 58 38 36 32 43 62 39 40 54 42 68 51 56 59 63 65 44 77 40 74 58 64 38 41 32 47 22 42 51 49 48 49 41 46 23 44 43 45 45 45 55 56 57 61 56 50 48 44 47 49 49 39 48 54 37 44 39 53 50 37 38 44 49 53 52 59 40 48 37 54 81 51 56 49 53 58 64 44 45 42 38 35 33 25 26 36 34 31 33 28 31 31 37 53 33 35 32 37 25 47 33 45 39 31 41 29 42 46 41 34 50 40 30 44 28 47 39 33 45 37 40 44 45 47 44 41 36 50 48 50 42 52 38 34 47 39 39 54 40 49 51 55 37 77 68 59 46 77 72 73 74 94 55 74 74 58 63 47 47 51 29 46 43 33 43 32 36 44 32 37 34 45 37 40 48 38 36 43 36 43 37 42 24 41 39 40 34 27 18 22 28 20 25 26 16 12 23 19 21 21 31 17 23 25 28 20 24 35 21 35 42 34 30 33 26 24 21 30 32 26 28 28 30 32 21 23 24 36 32 29 26 27 29 22 18 33 19 27 23 19 25 19 20 20 15 24 16 24 26 19 25 27 24 33 25 21 37 23 19 18 23 27 37 23 29 26 38 21 21 19 21 29 13 22 31 34 26 18 21 23 17 30 32 28 27 29 30 28 35 20 36 30 20 25 30 26 25 32 21 16 25 23 30 17 24 24 30 16 24 26 27 16 17 16 21 19 11 23 16 13 9 11 5 17 14 10 16 9 19 21 7 10 17 14 10 19 9 13 8 19 10 14 7 10 9 19 13 9 8 6 10 15 5 13 12 11 10 11 10 11 8 11 9 12 17 16 15 12 16 27 21 18 11 11 21 24 23 12 22 14 18 24 15 13 25 22 10 18 9 25 12 22 16 13 16 15 11 17 12 14 16 19 12 17 15 11 7 19 15 18 9 11 15 10 8 9 12 12 12 14 13 12 10 12 15 17 9 15 9 24 11 13 17 16 9 8 14 8 9 9 16 16 18 18 16 11 11 16 14 12 29 17 17 14 22 14 22 22 18 23 20 14 15 12 21 21 28 23 30 20 21 28 24 26 22 25 24 24 27 19 16 13 18 12 10 18 17 15 19 17 20 16 18 18 13 21 16 20 21 16 11 14 13 23 17 12 19 11 12 10 15 8 11 10 10 13 17 18 16 16 14 13 25 15 9 21 5 19 16 21 21 17 20 22 19 20 34 17 29 28 28 29 31 25 34 17 26 15 14 19 16 19 27 12 14 14 22 15 13 17 15 11 10 9 14 13 14 11 11 17 15 14 14 17 14 22 15 16 14 16 19 11 20 20 16 6 
];
B = [
0 0 0
 213448 150391 63057
 254779 196986 57793
 222369 172273 50096
 372350 318394 53956
 148573 116677 31896
 627437 573267 54170
 227061 201798 25263
 84055 68201 15854
 199772 183294 16478
 63772 53101 10671
 33648 26578 7070
 26966 21564 5402
 36661 31552 5109
 266914 254883 12031
 255779 244209 11570
 136892 127381 9511
 757825 733237 24588
 180161 169816 10345
 324129 311917 12212
 120441 113356 7085
 346760 335656 11104
 336319 325791 10528
 121262 115173 6089
 332749 322913 9836
 123222 117622 5600
 572770 557873 14897
 347608 337878 9730
 118139 113225 4914
 349295 339855 9440
 117050 112517 4533
 353649 344768 8881
 339661 331137 8524
 123297 119087 4210
 428048 417624 10424
 133023 128682 4341
 339332 330783 8549
 124434 118952 5482
 336452 328632 7820
 335909 327876 8033
 138216 132896 5320
 324409 316933 7476
 132760 127980 4780
 349409 341673 7736
 314189 307142 7047
 123691 119392 4299
 320044 312943 7101
 132793 128296 4497
 313518 306671 6847
 132046 127816 4230
 292506 286140 6366
 320042 312718 7324
 109820 106652 3168
 300120 293229 6891
 108893 105903 2990
 300325 293261 7064
 267883 261592 6291
 136592 133475 3117
 284904 278373 6531
 107641 105238 2403
 24856833 24563120 293713
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
55 43 3 1
35 8 1 0
36 26 0 0
51 27 1 0
29 21 2 1
29 29 1 1
744 43 10 4
4950 44 30 14
22003 46 159 40
88672 80 244 72
275241 81 320 104
799030 102 416 176
1909093 143 487 249
3884967 212 587 349
5991763 295 641 458
7388316 355 669 564
7086824 418 794 703
5408249 595 829 840
3097171 708 1030 995
1200987 915 1211 1143
253652 1159 1343 1390
22217 1354 1645 1616
3075 1677 1824 1885
2639 2037 2029 2117
2688 2252 2343 2276
3010 2700 2548 2497
3254 3111 2792 2763
3744 3678 3003 3117
3919 3851 3265 3403
3939 3877 3377 3680
6038 5495 3704 3674
4854 4801 3839 3904
4654 4594 3820 3995
4316 4263 3769 3933
4599 4990 3748 3823
4641 4940 3779 3844
4182 8321 3572 4106
3858 4005 3499 3505
4184 4286 3623 3510
3853 3925 3572 3550
4247 4003 3653 3574
3968 4051 3729 3801
5023 4690 4515 4652
4119 4084 4151 4063
5338 5148 4129 4118
4915 4912 4235 4191
4401 4390 4319 4263
4201 4233 4191 4176
4214 4199 4360 4355
4088 4004 4252 4224
3880 3926 4151 4234
3557 3464 3772 3782
3318 3429 3472 3510
2927 2916 3191 3186
2495 2471 2556 2658
2283 2438 2389 2461
2041 1959 2299 2443
1903 1926 2236 2323
1570 1582 1968 1855
1612 1628 1836 1877
1498 1459 1442 1445
1556 1445 1546 1444
1311 1360 1553 1608
1352 1461 1507 1504
1423 1458 1633 1585
1413 1371 1422 1479
1403 1398 1495 1450
4494 4289 2836 3201
1660 1625 1814 1845
1820 1808 1875 1902
2333 2254 2422 2400
2164 2285 2885 2661
2364 2401 2329 2420
2392 2323 2448 2432
2360 2425 2288 2326
2426 2472 2294 2190
1942 1916 1844 1834
1541 1556 1588 1529
1387 1387 1337 1387
1082 1067 1122 1047
688 692 704 740
418 415 499 475
20 16 23 20
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
