A = [
381343 391021 1723556 263256 268425 242362 232850 230924 224132 213044 209607 206826 203279 199840 196534 193658 190364 188792 186881 185737 183584 181725 180062 180179 182871 233941 234243 236601 288923 288731 292359 293340 295001 298096 299118 296855 294884 292356 291262 286747 285823 284153 284339 283261 282681 279995 278034 276389 272845 270358 268623 267041 266371 264845 263565 262628 260429 257893 256065 254502 251689 249950 249205 247813 245355 243758 244107 241556 240790 237659 235522 233244 231921 229392 228071 227191 224858 223676 221854 220585 219204 216354 214382 213250 211634 209750 208396 206809 204926 203551 200734 200177 198293 196740 194960 193167 192177 191782 188901 187884 185592 185014 182154 180976 179687 178286 177705 177251 174026 173668 171729 168993 168257 166894 165688 165128 163800 161591 160175 158465 158555 155822 153687 151920 151187 149855 148809 146615 146051 145261 143710 142327 141399 140063 138668 136916 135171 134822 133762 132509 131332 130158 129166 127852 126242 125246 124112 123178 122229 120651 119600 118650 117699 117086 115482 114451 113718 112616 110702 109622 109079 107719 105855 105059 104098 102723 101181 101050 99228 98869 97816 96189 95288 95097 93829 93181 91821 90186 89596 88714 88626 86973 86465 85498 84254 84156 82577 81941 81000 79810 78942 78837 77228 76425 75885 74392 74322 73336 72150 71971 71309 69794 69786 68227 67539 66812 66030 64837 64393 63347 62690 62313 61775 60645 60280 59416 58863 58007 57362 56967 56228 55079 54792 53480 53268 52340 51351 51279 50481 49479 49160 48682 47967 47367 46809 46663 45679 44535 44241 43593 43304 42592 42058 41963 41375 40961 40628 39844 39581 39069 38352 38072 37453 36868 36841 35382 35175 35037 34476 34153 33658 33029 32621 31943 31609 31309 30625 30515 29914 29610 29311 28870 28199 28335 27875 27273 27066 26550 26401 25717 25877 25539 25257 24856 24429 24256 23600 23704 23317 22739 22337 22468 21702 21694 21077 21380 20729 20392 19974 20020 19848 19676 19379 19229 19018 18584 18405 17961 17821 17381 17439 16976 17064 16162 16420 16111 15767 15642 15142 15490 15102 14481 14151 14027 14093 13869 13441 13008 12880 12792 12533 12407 12278 12157 11862 11877 11766 11318 11387 11082 10990 10956 10835 10728 10401 10202 10224 10141 9844 9631 9641 10426 9557 9378 9462 9142 10373 8764 8792 8802 8461 8552 8277 8190 8028 7801 7700 7695 7491 7420 7373 7239 7087 6994 6915 6877 6718 6729 6620 6485 6334 6330 6058 6144 6295 6155 5979 5893 5945 5786 5883 5631 5760 5735 5632 5574 5163 4932 5010 4976 4876 4878 4729 4622 4537 4572 4468 4381 4452 4305 4053 4154 4023 4174 4074 4029 3917 3766 3725 3712 3723 3686 3629 3577 3563 3480 3407 3502 3308 3305 3114 3155 3286 3177 3141 3036 3079 3003 2974 2885 2769 2763 2745 2687 2724 2575 2759 2590 2543 2520 2471 2594 2415 2443 2401 2394 2335 2470 2298 2255 2153 2187 2057 2085 2081 2024 2047 1980 2083 2018 1893 1964 1951 1955 1947 1883 1842 1865 1716 1666 1717 1809 1694 1664 1662 1659 1623 1601 1703 1619 1662 1574 1639 1565 1593 1554 1457 1470 1546 1478 1492 1448 1390 1388 1376 1360 1427 1340 1350 1285 1339 1288 1270 1293 1270 1238 1215 1131 1154 1180 1198 1115 1144 1210 1078 1138 1108 1060 1129 1110 1093 1102 1116 1043 1067 1092 1054 1121 1051 1121 1090 1058 1033 1056 1002 1154 1032 1158 984 923 988 973 943 937 964 996 938 948 935 916 883 911 887 963 958 779 788 781 776 770 827 766 853 874 902 927 869 788 813 794 760 698 754 757 731 747 756 705 705 709 687 701 707 724 720 677 705 710 705 626 619 631 664 651 657 616 623 608 610 604 592 579 633 606 538 600 592 579 590 568 513 502 538 496 509 545 532 522 545 510 530 491 536 519 501 494 510 488 522 507 477 513 502 501 464 435 428 426 423 431 505 432 451 452 446 438 410 450 456 448 436 414 402 419 413 431 442 407 444 400 428 394 394 402 357 370 363 390 399 400 330 403 408 333 365 339 341 349 349 362 352 402 378 366 368 331 349 317 359 357 339 325 356 318 352 387 354 337 353 329 321 344 360 326 314 295 330 358 341 361 370 360 325 331 348 346 350 310 358 354 325 371 341 386 405 462 552 399 422 444 361 334 379 398 316 368 434 344 401 359 333 351 352 347 290 312 311 317 290 287 303 248 250 267 288 273 306 258 285 304 315 308 287 359 292 336 303 296 293 262 258 303 278 277 260 284 297 294 249 268 235 262 211 258 239 263 249 233 255 255 240 232 222 258 254 240 233 242 260 203 226 215 222 230 213 203 203 241 227 235 221 170 186 215 193 245 186 204 224 194 200 204 224 201 205 229 227 231 218 247 227 250 212 191 195 218 208 195 206 194 179 192 199 190 197 203 189 195 167 166 160 169 162 149 179 157 147 173 190 150 161 146 165 195 177 181 202 171 169 170 194 186 187 207 171 161 144 162 152 165 148 158 144 158 140 129 167 143 146 146 121 139 132 132 157 136 161 144 127 127 151 119 124 157 149 139 150 146 169 157 246 145 140 137 134 128 110 123 139 126 135 155 135 124 115 120 113 111 127 122 107 106 110 99 87 108 97 118 110 103 131 102 107 116 126 105 110 113 106 101 103 86 103 98 80 83 104 90 80 87 90 91 92 85 95 88 66 92 86 93 122 94 81 109 96 106 101 88 98 101 93 86 89 103 94 109 105 106 86 96 102 102 74 88 97 104 104 63 81 90 64 56 67 82 84 75 81 94 80 92 67 90 100 99 104 74 77 70 88 80 79 72 76 90 75 85 72 87 79 70 72 79 75 76 67 83 110 97 83 83 69 85 61 72 59 85 108 87 96 90 83 73 82 77 68 89 85 70 93 81 65 71 91 88 75 72 70 83 63 71 69 70 79 75 74 91 47 72 67 68 80 80 78 71 83 59 72 69 64 62 73 84 64 54 51 73 71 69 78 66 51 68 55 47 64 65 58 68 55 66 64 64 61 80 64 69 76 61 63 66 67 59 75 66 60 62 68 58 65 58 78 58 53 54 59 56 58 61 59 49 55 70 58 71 65 64 59 67 51 50 66 53 59 52 74 68 61 52 52 76 58 58 67 55 63 76 55 54 56 64 56 48 54 59 61 48 72 67 52 43 47 56 56 58 61 56 48 57 60 53 51 53 47 40 39 36 38 38 23 34 44 47 40 31 36 46 43 39 53 29 27 38 39 28 38 34 32 37 36 42 48 36 35 29 39 32 34 41 45 34 34 44 44 36 45 33 46 27 34 34 33 34 36 30 36 36 41 34 45 38 32 40 29 36 28 31 29 42 25 41 35 35 34 41 30 28 36 34 37 35 37 35 27 30 49 39 39 22 36 27 42 29 41 34 31 42 27 42 35 35 38 33 32 26 27 26 26 32 43 30 28 36 21 23 31 22 27 24 28 34 32 37 21 23 27 17 28 25 21 26 25 18 23 24 31 21 26 26 26 19 19 29 29 17 18 15 26 23 25 17 22 22 24 18 23 30 25 17 27 26 22 18 27 23 14 20 20 20 16 24 16 22 22 20 13 21 13 15 25 17 35 14 20 15 21 18 16 23 31 21 19 15 16 21 23 16 22 25 23 14 9 17 17 12 19 27 27 28 33 27 42 25 39 40 29 54 42 37 33 30 30 24 30 23 19 27 26 23 26 28 23 25 23 26 31 24 18 27 25 23 23 28 31 27 25 29 28 23 26 15 18 23 15 20 24 17 21 21 21 20 17 17 30 26 22 18 13 16 23 19 16 16 18 21 17 6 16 12 23 13 13 16 16 15 10 16 24 19 11 11 15 22 14 21 20 18 20 21 18 21 20 16 15 21 22 13 19 17 16 16 10 15 26 20 15 17 9 14 21 19 8 22 23 15 19 14 20 16 8 13 17 15 15 17 18 11 16 17 13 9 19 14 20 14 20 13 11 15 20 19 11 11 10 19 10 19 14 9 15 11 7 14 11 14 24 8 24 10 12 12 15 8 9 6 9 9 8 6 13 15 15 13 14 11 11 9 10 14 12 11 10 11 8 11 14 17 18 13 11 20 12 16 12 15 19 11 24 22 23 16 14 16 11 11 15 19 10 18 16 22 18 20 14 19 9 16 13 10 26 13 13 25 16 29 22 21 22 21 17 20 11 14 22 14 9 8 11 6 14 19 18 10 8 12 12 12 11 17 12 13 5 16 16 12 14 11 16 13 13 7 17 14 8 19 14 13 11 48 63 96 92 73 59 51 65 27 9 13 14 7 9 4 8 12 9 15 8 10 13 8 10 15 16 10 11 12 11 8 16 14 8 13 19 16 30 18 22 22 15 19 17 14 10 10 8 10 10 10 14 4 7 10 18 10 5 12 13 9 12 10 16 10 7 11 10 10 11 8 7 12 16 6 8 6 10 7 11 11 9 8 7 10 11 9 8 13 11 7 10 7 7 12 8 12 10 12 12 20 12 15 11 8 9 13 6 8 9 7 6 7 11 9 7 10 7 11 10 7 7 5 4 8 6 8 8 8 7 6 9 7 7 5 9 5 5 9 3 2 8 6 10 7 5 7 5 4 5 10 6 4 10 4 3 12 10 11 13 6 13 8 4 11 6 10 11 13 9 13 7 8 11 14 5 9 10 4 7 7 8 9 10 15 8 15 8 10 10 8 10 10 10 14 9 13 12 10 7 6 8 7 5 12 9 15 5 6 8 9 4 4 9 10 9 13 9 11 8 10 13 7 8 11 13 6 3 6 10 8 6 8 6 6 7 4 4 13 7 8 6 11 4 7 9 6 8 2 6 11 10 10 3 2 6 5 2 7 4 7 4 4 9 5 7 5 3 7 6 4 7 8 6 4 8 11 6 4 6 10 11 5 10 8 11 4 9 9 6 7 5 8 5 9 8 6 6 9 4 6 6 5 9 4 4 6 14 3 8 5 9 10 7 10 6 9 3 6 7 9 8 7 
];
B = [
0 0 0
 124517 31726 92791
 59620 15338 44282
 205223 59994 145229
 132643 35361 97282
 78278 20306 57972
 202600 60926 141674
 161924 44978 116946
 92146 24655 67491
 277783 82306 195477
 290003 80257 209746
 51627 13793 37834
 835053 248806 586247
 110259 32182 78077
 34871 9859 25012
 188834 66397 122437
 60351 20334 40017
 18480 5666 12814
 209643 74145 135498
 16905 5115 11790
 17593 5540 12053
 4123 1360 2763
 90 25 65
 3971 1332 2639
 309822 113038 196784
 20334 6426 13908
 26122 8823 17299
 322416 120176 202240
 18677 6587 12090
 39258 13843 25415
 510428 182017 328411
 36485 13093 23392
 65307 23573 41734
 361621 141705 219916
 235742 91556 144186
 391605 153550 238055
 732335 287813 444522
 597911 224756 373155
 363200 140090 223110
 852411 342845 509566
 339587 125915 213672
 23010 8839 14171
 790497 317793 472704
 12546 4710 7836
 22369 8324 14045
 1077587 445354 632233
 22947 8880 14067
 273200 102781 170419
 1478664 649029 829635
 268696 103214 165482
 5 2 3
 10143864 4614426 5529438
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
27 63 1 1
24 10 0 0
47 12 0 1
85 9 0 0
68 16 1 0
50 15 14 1
161 40 49 6
552 48 68 13
2575 42 104 31
9537 74 122 53
21338 82 151 69
44059 119 212 126
85040 160 318 191
168541 218 431 305
313052 295 554 474
561701 512 830 741
790477 819 1193 1098
777238 1386 1538 1563
556887 2310 2085 2098
299712 3120 2646 2502
121165 3945 3045 2960
31193 4732 3217 3342
7760 4632 3560 3352
5706 4238 3649 3483
5280 4291 3641 3724
5046 4615 3576 3717
5046 4030 3830 3758
4918 4116 4007 4024
5072 4465 4289 4285
5223 4638 4526 4495
5322 4718 4728 4892
5875 5424 5186 5298
6271 5945 5674 5662
6893 6463 6136 6302
7615 7113 7066 7008
8309 7943 7757 7739
9325 8815 8653 8938
10332 9906 9712 9871
11267 11099 11024 11180
12600 12650 12705 12731
14408 14326 14347 14433
16332 16046 16164 16264
18386 18333 18421 18217
20809 20935 20806 20819
23882 23546 23624 23819
26861 26537 26864 27143
30082 30233 30176 30460
33918 33735 34055 33405
37850 37391 37695 37581
41917 41779 41589 41448
45117 45310 44897 44667
47879 47984 48016 48061
50834 50906 51028 50703
53408 53411 53116 53887
56121 55935 56487 56223
58361 58603 58272 58733
62057 62347 62104 61468
64974 64752 64445 64309
68055 67625 67853 67403
70681 70628 70394 70586
73455 73699 73418 73487
74186 73868 73656 73525
70986 70446 70787 70568
61769 62086 61390 62430
46156 46428 46600 45624
25938 26098 26260 25515
11247 11629 11509 11014
6540 6539 6727 5899
5420 4864 5169 4907
4434 4508 5296 4136
3271 3320 3138 3377
2268 1880 2092 2233
187 169 156 130
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
