A = [
323632 316571 1959686 290141 278224 262080 250250 249322 242641 226030 223400 220157 215558 212289 209119 205637 202997 200237 198860 196468 195347 193116 191320 190469 194462 258861 257449 260338 324614 325202 330190 333670 334561 339277 341796 338963 334475 331508 328315 324142 323050 322114 321373 321038 320924 317869 314961 311436 307885 305775 302707 301218 300955 301876 299153 297825 295201 292011 289906 285952 284295 282605 281173 280336 279180 277008 275784 273762 270220 267839 265338 263989 262054 259159 257125 256828 254656 252337 249834 247423 245284 242833 241610 240281 238507 236784 234145 233236 230152 228081 225730 223618 222194 220631 218880 218535 215813 214305 214226 210764 208763 207283 204312 203846 203934 201527 199800 199490 196203 195732 193638 191741 189270 188058 186944 185214 184627 182251 180702 179342 177983 176277 174112 171808 170133 169855 168814 167537 166383 164274 162506 161581 160722 159356 157611 155525 155383 153466 152070 151031 149487 148159 147041 146367 145072 144166 142145 141709 139676 139098 138039 136394 134308 133188 132376 131033 130383 129251 127954 127403 125049 124708 121519 121168 120018 118803 118130 117134 116193 114627 114033 112538 110559 110149 109222 108096 107021 105995 105435 104183 103467 101704 100849 99928 99717 97874 97505 96121 95815 94559 94055 93270 91753 90362 90093 89231 87481 86509 86776 85569 84487 83479 82313 81582 80559 80010 78606 77830 77222 76111 75739 75335 74102 72863 72319 71743 71169 69724 68887 68700 67786 67012 66305 65362 64116 63800 63086 62520 61554 60733 60544 59499 58799 58085 56808 56812 55840 55057 54517 53295 53562 52370 51807 51559 51001 50465 50145 49454 49011 48162 47965 47008 46385 45954 45233 44579 44262 43401 42727 42779 41918 41419 41184 40702 39957 39155 38940 38051 37783 37112 36728 36371 35675 35646 35149 34296 34133 33761 33328 32975 32428 31939 31405 31647 31243 30684 30133 30000 29531 28728 28552 28047 27433 27204 27064 26719 26295 25949 25836 25666 24924 24641 24585 24723 24307 23402 23415 22748 22736 22164 21810 21519 21602 20882 20982 20563 20252 19694 19413 19175 19398 18350 18043 17755 17452 17415 17212 16525 16408 16304 15967 15840 15588 15162 15293 14591 14604 14482 14518 14309 14363 14078 13795 13758 13436 12991 12900 12869 12653 12310 12300 13343 11949 11649 11996 11554 13043 11297 10972 10848 10648 10729 10532 10172 10009 10086 9683 9604 9287 9416 9233 9197 8990 8844 8474 8733 8565 8239 8120 8062 7924 7946 7777 7727 7917 7572 7485 7547 7459 7130 7198 6963 7274 7146 7038 6769 6303 6263 6086 6000 6042 5900 5808 5935 5683 5857 5656 5529 5177 5269 5237 5052 5095 4955 4926 4909 4834 4748 4686 4463 4388 4408 4420 4355 4155 4137 4260 4075 4086 3962 3851 3858 3931 3743 3743 3718 3638 3524 3526 3378 3304 3196 3333 3171 3130 3145 3018 2981 3017 3014 2866 2879 2838 2882 2819 2800 2749 2615 2558 2549 2485 2515 2510 2461 2543 2393 2344 2469 2363 2299 2362 2247 2267 2231 2117 2140 2108 2032 2016 2053 1928 1920 1970 1943 1887 1991 1895 1864 1865 1702 1789 1779 1766 1766 1724 1758 1669 1647 1646 1597 1578 1631 1499 1588 1492 1602 1561 1488 1534 1429 1389 1398 1417 1390 1417 1353 1367 1363 1288 1281 1292 1284 1255 1243 1273 1189 1237 1149 1205 1237 1148 1234 1125 1169 1189 1124 1142 1157 1079 1187 1142 1106 1156 1108 1122 1159 1091 1241 1140 1082 1140 1051 1000 1042 998 973 979 1058 1002 1011 926 966 921 1021 958 854 858 858 875 795 836 847 905 1016 944 940 985 879 870 847 839 826 768 851 822 735 726 761 768 751 747 753 732 832 755 718 710 761 769 770 618 632 658 653 648 653 630 647 672 665 619 581 601 566 575 570 571 548 595 582 563 516 579 584 543 509 488 532 511 554 545 523 564 536 457 550 511 536 467 533 483 491 494 505 486 467 443 449 422 448 417 450 413 489 436 468 467 450 412 387 432 400 422 435 497 415 439 423 446 438 418 393 398 366 391 376 405 385 365 354 361 349 332 373 378 343 362 371 351 355 355 412 358 360 345 362 355 347 317 351 329 375 329 346 393 371 319 394 354 349 337 332 331 306 294 296 338 342 380 352 330 365 352 355 351 347 329 318 343 376 361 379 397 375 434 538 473 418 487 487 359 392 413 488 419 363 478 379 372 396 411 485 394 324 326 328 350 323 316 276 294 273 257 256 257 277 297 291 285 295 324 324 287 347 323 310 301 259 286 297 263 302 309 272 281 246 278 316 259 240 258 257 234 214 198 251 291 249 283 240 261 258 240 248 257 230 217 211 284 232 215 230 227 255 222 199 218 217 216 221 216 217 225 192 185 258 220 232 219 237 244 227 226 230 221 218 212 229 226 201 234 224 252 207 220 218 204 232 196 177 208 193 213 193 174 204 202 177 182 143 188 148 161 161 152 128 154 181 183 162 181 183 172 192 179 173 196 202 191 204 173 201 195 181 193 172 161 143 165 158 142 168 137 159 160 146 165 148 161 150 134 167 137 126 137 144 138 163 159 136 130 136 145 121 143 162 137 141 156 165 315 170 138 143 133 139 122 160 133 136 143 135 107 128 145 122 135 118 121 111 102 103 103 110 107 88 115 135 122 95 101 105 99 104 125 109 103 106 119 110 97 119 95 112 106 86 99 83 104 91 79 88 86 91 95 101 78 81 93 94 121 122 95 82 96 105 84 99 101 121 84 91 76 118 84 89 102 85 110 119 95 111 87 105 91 87 95 96 91 109 71 76 83 84 85 70 59 75 95 70 91 70 82 75 75 74 95 60 74 78 102 89 75 74 72 92 80 76 67 76 78 75 61 51 57 69 92 84 91 71 92 93 77 74 71 100 83 105 75 106 70 82 95 84 73 92 76 69 76 77 66 63 79 79 79 73 95 82 63 78 62 68 72 69 75 62 72 72 67 77 62 72 59 61 81 81 77 87 50 60 65 61 67 65 57 49 70 53 45 63 58 62 57 41 70 66 65 43 55 65 70 76 61 60 55 67 62 62 62 73 53 65 64 74 58 65 45 56 68 70 42 49 58 51 44 50 45 55 52 55 41 34 54 48 56 64 46 70 59 60 53 60 58 59 81 51 71 64 60 52 64 59 56 52 70 63 65 51 58 47 58 56 64 69 66 63 60 63 62 59 54 55 57 59 47 54 53 47 46 56 53 48 64 41 30 39 49 35 36 43 29 39 39 42 41 33 35 42 35 49 31 54 35 38 36 31 31 30 34 30 38 42 33 36 22 33 32 34 26 24 38 42 36 32 28 41 35 35 36 34 34 26 23 34 34 40 31 29 26 49 38 39 32 32 43 24 30 25 34 38 39 25 33 29 32 34 34 32 27 34 45 31 31 37 35 40 41 29 22 29 28 34 34 31 32 34 39 29 35 37 38 29 33 29 35 18 23 30 30 30 25 30 31 22 21 19 33 26 30 29 34 29 23 27 23 19 24 12 19 25 22 10 13 15 21 20 26 23 11 22 27 34 26 23 27 27 24 19 19 18 23 11 24 16 37 25 16 18 24 15 28 21 17 21 33 18 17 24 18 13 13 13 17 16 18 18 21 15 21 12 22 25 14 20 21 18 17 18 32 19 13 31 23 16 25 36 23 20 27 14 22 24 22 16 24 27 30 30 32 30 41 29 29 39 40 35 38 27 34 27 27 31 29 33 25 31 26 28 18 25 28 29 29 29 27 29 24 35 28 27 22 36 32 30 22 34 12 24 28 27 19 20 28 18 27 17 23 15 17 22 14 20 9 19 19 24 22 12 20 15 24 16 18 26 13 15 11 12 18 16 16 17 12 15 7 14 10 12 10 17 15 13 6 21 16 19 9 10 9 12 10 12 19 22 20 23 17 17 15 22 16 19 10 20 19 8 11 10 8 19 11 19 9 16 20 23 10 8 14 5 10 11 17 20 13 16 13 14 16 14 13 14 5 13 13 8 14 16 12 17 11 12 6 12 11 11 7 9 14 12 11 9 14 8 16 9 12 15 8 17 8 5 6 10 10 15 9 6 13 12 13 12 10 12 13 8 13 13 11 12 10 15 9 16 15 11 21 12 17 11 17 11 15 20 9 11 12 11 22 12 13 13 12 16 17 13 15 13 16 12 25 15 3 7 10 14 14 7 13 20 20 21 21 28 26 16 17 14 24 19 16 15 19 4 7 10 13 7 8 11 13 6 10 6 13 11 20 11 7 5 15 13 15 13 13 10 13 9 8 11 9 8 12 19 7 15 14 70 80 82 90 91 56 71 98 16 14 12 8 7 6 12 7 10 2 6 8 8 6 6 11 9 8 7 10 7 21 10 17 12 13 5 19 12 19 16 16 23 14 18 8 8 11 7 7 8 8 7 12 9 12 13 15 6 14 9 6 8 5 9 8 12 7 8 18 11 11 7 14 6 7 11 13 3 7 7 10 7 3 6 10 4 6 12 7 8 4 8 10 10 8 6 8 9 5 8 9 7 10 7 6 8 4 8 8 5 2 6 8 4 9 3 7 5 4 6 4 4 2 8 6 6 7 8 2 7 5 4 6 5 6 4 7 7 8 3 4 5 7 8 6 3 4 5 7 6 6 6 3 6 4 6 5 10 4 6 7 4 6 10 6 7 10 6 6 7 11 10 8 8 12 9 14 3 11 5 4 7 4 4 11 6 12 7 8 4 8 9 16 14 6 10 5 8 1 7 4 11 8 7 8 10 3 9 9 14 7 8 7 6 7 5 9 7 6 11 8 8 4 6 6 6 6 7 9 8 5 6 3 6 7 9 6 6 7 5 10 7 10 6 4 1 9 8 9 6 13 6 10 7 8 6 4 5 6 2 4 3 6 3 5 6 8 9 4 9 4 1 6 7 6 4 6 8 6 4 5 5 6 8 4 6 7 4 1 7 8 10 10 6 10 8 4 4 6 6 7 8 5 7 5 5 3 2 5 1 6 4 5 4 9 7 7 9 8 4 6 10 2 5 
];
B = [
0 0 0
 143839 30908 112931
 68289 15120 53169
 234377 57465 176912
 153341 34622 118719
 91883 20378 71505
 232279 58972 173307
 188268 44749 143519
 106644 24434 82210
 320565 80209 240356
 337359 79571 257788
 61174 13973 47201
 967569 241455 726114
 129404 32252 97152
 41440 10150 31290
 218044 64592 153452
 70831 20381 50450
 22019 5823 16196
 241713 71904 169809
 20150 5278 14872
 20996 5897 15099
 5069 1435 3634
 114 30 84
 4801 1372 3429
 358933 111800 247133
 23784 6455 17329
 31041 9011 22030
 371652 117813 253839
 21905 6690 15215
 46777 14289 32488
 593324 179564 413760
 44042 13714 30328
 78301 24398 53903
 418306 138828 279478
 279352 92445 186907
 462420 154651 307769
 852467 284778 567689
 710000 231506 478494
 430321 141334 288987
 991967 340440 651527
 402869 131264 271605
 27624 9081 18543
 912729 314427 598302
 15051 5037 10014
 26332 8687 17645
 1241809 437376 804433
 27451 9237 18214
 320350 105321 215029
 1672224 615618 1056606
 317651 105208 212443
 11 6 5
 11192742 4235953 6956789
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
18 56 0 1
10 3 0 0
27 6 0 0
51 11 0 0
42 10 0 1
43 16 15 2
98 22 37 6
332 33 56 10
1195 21 55 25
3884 33 92 41
8577 45 123 65
17963 72 143 95
35251 112 231 147
71442 158 328 227
137476 237 409 343
264685 440 610 605
438467 879 960 899
523983 1692 1350 1330
435598 2778 1899 1851
254330 3719 2408 2383
101872 4560 2939 2919
24679 4764 3306 3301
6647 4379 3506 3499
5445 4326 3692 3646
5076 4324 3924 3877
5080 4692 3898 4113
5161 4172 4092 4021
5198 4294 4355 4248
5422 4682 4766 4681
5485 4986 4907 5172
5865 5285 5463 5649
6459 5815 5752 5872
6777 6328 6333 6355
7411 7120 6825 7078
7986 7857 7695 7755
8861 8670 8808 8663
9891 9676 9702 9656
11181 10936 10974 11120
12515 12406 12542 12206
14131 13907 14023 14021
15957 15870 16357 15818
18493 18390 18185 18342
20655 20722 20802 20719
23524 23907 23570 23936
26794 27169 27113 26838
30749 31051 30535 30884
34684 34640 34655 34196
38166 38575 38323 38546
42633 42685 43203 42929
47366 47127 46812 47070
51111 51631 51559 51470
55085 55079 55227 54950
58986 58475 58732 58373
62515 61927 62504 62024
66364 66022 66566 65974
69703 69295 69766 69452
74326 74762 74398 74176
79155 79578 78742 79355
84281 84717 84644 84069
88189 88314 88969 88129
93259 93757 93359 92427
94181 93517 94019 93934
90852 90125 90639 89801
78522 78260 78320 78277
58073 58386 58250 57571
31812 31838 31982 31955
13383 13846 14030 13219
7508 7572 7940 7198
6203 6050 5980 5580
5344 5318 6279 4949
3722 3812 3648 3968
2593 2223 2281 2621
188 175 164 170
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
