A = [
563117 558225 2903258 456877 443371 414514 395523 390145 379530 358489 352490 346594 339267 333980 329210 323627 319185 315656 312720 308937 308138 304739 302635 301344 307618 416329 416715 421191 531289 532952 538839 544814 546547 554375 556895 554495 547277 542462 538221 531743 530815 528296 526978 525179 524644 518940 514886 508664 504273 501884 497452 494164 491851 491430 488239 484680 482369 477877 475053 469495 467109 463309 460946 460357 456817 454804 452818 449247 445622 440481 437088 434176 431326 428999 425227 424806 421463 417487 412857 408740 405699 402292 399724 397876 395276 392178 388072 386773 383304 379200 376229 371881 369654 366828 364141 363029 359717 356163 354568 349452 346460 344053 339071 337481 336616 332557 330836 329429 323648 322087 319483 316668 313248 310619 308791 304847 301772 299172 297688 294977 292628 289461 287026 283427 281646 280026 276967 275342 273651 269740 267858 265613 263198 260702 257643 255219 254152 250737 248707 246287 244267 241180 239491 237496 234860 233300 230900 228994 226181 225720 224609 221372 218201 216236 214016 212755 210217 209162 206367 205507 202687 200573 198311 197005 194571 193194 191227 190041 187861 185508 184122 182110 179406 177989 176458 174482 172279 170594 169106 167146 166118 163318 161547 160746 159082 156861 155792 153489 152308 150934 149367 148663 146075 144068 143435 141543 139754 138063 137129 134991 133297 131995 130509 129443 127707 126975 124788 123348 121984 120672 119352 118239 116811 114414 113169 112031 111087 109312 108115 106657 105164 104331 103668 102177 100859 99551 98334 97526 95787 94146 93691 92434 91657 89816 88256 88165 86676 85399 84606 82559 82636 81494 79962 79350 78332 77759 76697 76014 75090 73760 72221 71881 71156 69724 69408 68054 67097 66271 65513 64956 64215 62814 62298 61396 60354 59619 59545 57882 57608 56445 55792 55225 54074 53445 53380 52113 51637 50946 50253 49919 48798 48111 47520 47695 46296 45643 45106 44532 43605 42755 42630 41908 41284 40580 40163 40094 39265 38692 38372 38224 36709 36230 36061 35604 35142 34119 34119 33136 33040 32337 32214 31903 31855 31027 30843 29976 29428 28864 28541 27963 28213 27010 26461 26312 26025 25835 25274 24473 24069 24023 23667 23311 22949 22324 22558 21744 21464 21276 21074 20868 20499 20153 19914 19928 19498 19039 18784 18556 18226 17992 17938 19645 17483 17097 17439 16829 19313 16469 16095 15846 15724 15373 15275 14727 14562 14627 14202 13939 13522 13622 13355 13198 12918 12507 12175 12193 11943 11602 11547 11323 11233 10978 10712 10615 11115 11004 10839 10813 10901 10418 10472 10156 10296 9939 9847 9600 8716 8558 8415 8297 8260 8448 8171 8298 8145 8055 7886 7634 7432 7398 7287 7031 7176 6939 6770 6684 6576 6587 6463 6216 6340 6071 6195 6088 6028 5765 5970 5734 5692 5544 5440 5368 5272 5250 5174 5076 4970 4750 4927 4676 4702 4551 4596 4548 4410 4389 4257 4219 4193 4208 3929 4017 3879 4054 3842 3785 3657 3626 3620 3465 3411 3434 3374 3364 3346 3233 3197 3206 3156 3047 3103 3035 3040 2960 2900 2809 2837 2809 2712 2729 2617 2590 2689 2618 2597 2618 2482 2458 2475 2341 2379 2362 2360 2337 2286 2266 2209 2091 2197 2102 2084 2185 2018 2102 2018 2084 2014 1981 1942 1878 1840 1911 1825 1892 1883 1820 1879 1783 1746 1730 1660 1628 1646 1671 1623 1562 1601 1568 1564 1618 1551 1569 1464 1524 1487 1447 1536 1464 1325 1362 1305 1257 1361 1302 1343 1310 1331 1291 1277 1263 1243 1254 1175 1244 1135 1107 1144 1214 1229 1198 1113 1153 1115 1121 1101 1054 1157 1067 1060 1060 1104 1075 999 1039 1034 949 978 877 945 929 933 975 890 993 869 873 858 857 855 839 832 844 848 901 815 805 847 824 769 777 759 758 778 779 769 736 705 792 767 781 714 694 741 654 661 621 663 664 675 655 692 657 711 647 646 621 610 636 597 627 594 644 668 618 563 622 605 605 580 629 551 564 557 572 532 544 474 572 497 555 512 537 532 513 508 525 534 519 466 457 464 475 470 491 483 495 480 498 493 474 471 424 467 408 437 440 422 415 402 370 441 405 399 413 401 436 378 423 401 384 439 398 384 384 369 397 389 411 385 367 415 450 391 406 425 426 418 440 386 426 387 387 385 367 323 346 380 363 366 351 362 359 345 402 382 366 354 375 392 379 414 396 379 394 379 389 394 448 455 514 402 443 551 642 451 453 442 379 370 376 366 396 364 294 283 289 288 292 316 281 271 324 283 286 320 281 305 303 251 282 300 318 264 299 281 286 303 295 284 295 263 312 315 305 286 284 304 301 275 297 288 279 264 254 246 253 294 257 268 249 282 227 207 195 219 212 208 213 220 222 217 226 224 246 221 209 229 223 265 264 241 246 248 219 212 220 239 241 234 233 248 229 216 206 216 196 207 220 201 205 199 222 223 216 216 194 195 214 191 171 195 202 187 169 152 202 176 161 148 170 181 151 154 177 149 159 177 181 186 173 181 165 137 195 168 165 169 170 181 196 203 205 183 173 187 169 165 167 172 163 151 168 161 157 164 160 172 139 157 141 131 153 125 128 151 151 174 171 168 137 127 163 145 124 144 184 143 151 145 152 157 167 140 142 161 138 151 151 152 148 149 151 124 116 127 110 134 112 114 113 104 101 124 130 115 99 107 142 131 115 111 116 91 107 126 92 110 120 134 124 116 114 86 120 116 107 100 85 115 102 89 93 85 83 92 80 80 86 73 77 92 89 66 71 75 91 75 81 90 73 66 87 93 132 83 89 102 81 103 88 92 81 83 79 78 77 74 84 78 86 69 75 96 78 87 73 69 75 83 73 73 66 91 83 77 72 91 66 80 90 112 101 84 81 81 90 93 71 66 79 75 70 56 59 61 69 68 71 100 78 85 90 58 65 88 76 89 97 74 88 63 70 95 72 64 75 59 68 62 65 70 53 68 65 48 61 71 57 51 52 54 64 62 50 63 55 64 76 58 67 75 70 64 56 69 64 53 60 53 71 58 62 77 39 40 52 65 53 41 47 56 60 48 38 65 63 62 36 52 60 63 64 57 55 61 55 50 63 48 58 47 63 55 62 50 58 48 57 55 54 33 43 54 41 37 46 46 51 47 60 44 37 50 46 49 43 43 47 54 64 58 62 46 47 74 38 71 54 46 59 54 61 50 40 56 58 57 48 50 60 61 46 60 60 62 59 63 70 68 68 64 62 56 63 65 55 56 55 53 49 47 42 59 37 38 37 42 35 38 44 32 43 34 44 35 36 47 39 34 35 28 39 39 31 41 31 34 31 30 30 37 33 32 30 18 24 19 28 28 23 33 38 28 34 32 40 43 33 31 30 32 23 27 42 29 47 27 22 28 47 34 29 31 25 36 26 32 20 33 21 28 31 27 26 31 44 31 29 24 34 37 32 34 38 32 30 46 27 29 28 29 42 30 23 33 38 29 27 39 41 37 37 34 31 33 30 24 32 36 28 28 35 32 28 17 22 21 16 24 26 28 24 26 22 15 18 19 13 21 14 16 9 17 12 24 26 27 20 10 20 19 25 22 16 27 31 24 24 23 19 15 20 18 22 26 22 17 19 19 14 23 21 15 19 22 14 18 19 10 14 11 11 16 10 14 14 18 11 15 9 15 12 11 14 9 11 16 11 29 17 21 22 12 18 21 25 23 20 25 20 25 21 21 20 26 30 24 24 27 29 36 18 25 28 24 26 37 19 25 35 27 27 36 44 35 36 29 37 34 33 35 29 34 38 33 31 32 40 31 22 16 31 35 27 24 18 12 15 20 19 14 15 25 23 21 13 17 19 14 14 13 16 6 18 12 13 15 8 10 12 23 11 16 11 11 11 6 12 11 12 22 12 10 10 7 13 10 9 7 13 11 12 6 11 11 10 8 5 7 7 18 8 10 12 7 16 8 11 4 10 14 15 6 6 10 5 4 9 7 10 8 14 5 11 14 13 8 9 6 9 4 7 11 10 6 4 10 13 17 6 16 7 7 6 16 7 13 16 10 12 12 8 8 14 8 13 6 6 11 9 11 10 8 7 4 5 18 15 12 19 5 6 8 7 5 11 7 6 6 7 7 3 10 8 8 6 7 8 7 11 12 13 4 9 13 11 11 8 9 9 17 18 18 22 13 14 12 14 13 15 12 18 6 20 14 14 17 10 5 5 13 5 6 2 5 8 11 8 2 7 6 12 4 4 8 13 9 9 9 5 11 8 9 5 4 11 7 7 10 15 9 7 6 9 9 6 15 3 3 4 14 13 10 11 7 6 7 7 7 8 9 5 6 12 5 8 9 10 11 8 11 10 8 10 3 8 10 8 6 4 7 7 8 11 4 4 4 4 5 8 7 6 4 5 10 5 8 7 6 7 6 1 12 4 5 8 6 7 2 8 8 5 4 8 10 9 4 3 7 5 5 4 6 6 6 3 4 5 2 5 3 5 4 8 15 8 4 4 9 3 6 7 3 1 3 3 7 2 5 4 3 5 1 5 3 1 2 4 0 5 3 4 7 2 2 6 4 4 7 6 4 7 1 6 6 1 2 4 4 2 6 1 4 5 1 3 2 5 1 4 7 4 2 7 4 2 1 2 4 1 5 5 6 5 5 2 4 1 7 9 6 2 3 2 3 3 7 2 3 5 3 5 3 6 5 3 2 4 4 8 2 3 6 2 5 7 12 10 7 6 5 7 11 3 7 2 6 8 4 3 9 6 6 7 7 6 5 7 10 9 1 7 3 3 4 3 1 6 4 12 5 5 4 8 4 6 7 6 11 5 3 1 7 5 5 7 10 7 6 6 5 5 2 8 3 8 3 6 3 8 5 5 4 6 5 2 5 4 8 3 6 3 5 8 4 3 5 3 8 6 2 3 5 4 4 3 6 0 5 3 3 3 1 8 3 1 2 1 6 6 2 1 7 7 2 4 3 6 3 4 3 7 3 4 1 5 2 4 7 4 11 10 6 4 2 2 9 3 2 4 2 2 1 2 4 2 1 2 4 5 5 3 7 5 7 5 4 6 4 2 
];
B = [
0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 1154888 336773 818115
 85499 25894 59605
 151277 45884 105393
 815880 261627 554253
 539057 172540 366517
 890789 286673 604116
 1654011 533718 1120293
 1384318 436447 947871
 829452 263140 566312
 1926486 637009 1289477
 791168 250134 541034
 54519 17338 37181
 1790297 596103 1194194
 29157 9436 19721
 51432 16538 34894
 2429034 824112 1604922
 53460 17317 36143
 631047 201459 429588
 3260613 1154452 2106161
 622334 200720 421614
 22 12 10
 21817428 7927308 13890120
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
32 96 0 2
16 8 0 0
45 10 0 0
55 12 0 0
35 18 1 0
34 23 30 4
93 31 58 7
326 27 94 18
1386 37 103 45
4584 56 152 64
10534 60 197 100
22966 113 250 154
46845 147 362 231
99402 239 481 403
199634 376 683 573
396203 739 978 960
645169 1548 1513 1449
749706 3079 2158 2161
626153 5196 3117 2998
385795 7258 3974 4003
173836 8738 4771 4762
46175 9194 5265 5262
10912 7912 5502 5561
8195 7062 5737 5852
7752 7320 6264 6039
7772 7559 6303 6496
7837 6928 6739 6671
8032 7062 7219 7115
8574 7539 7901 7800
8943 8159 8274 8380
9584 8661 9090 9224
10227 9488 9764 9876
11239 10437 10664 10766
12264 11724 11815 11882
13453 12932 13102 13081
14937 14540 14897 14666
16635 16242 16537 16213
18710 18490 18496 18673
21008 20825 21108 20810
23802 23684 23743 23733
26926 26833 27196 26771
31231 30939 30691 30886
35113 35017 35134 35241
39741 40085 39846 40067
45341 45511 45496 45275
51728 51919 51604 51892
58119 58486 58223 57813
64463 64729 64704 64730
71391 71803 72104 72396
79510 79172 79084 79115
86394 86700 86802 86520
92832 92685 92867 92248
99285 98219 98655 98519
104905 104462 105075 104217
111611 110955 111908 111286
117675 117522 117284 117306
126085 126611 126309 126124
134201 134564 133433 134457
142854 142981 143517 142361
150263 150049 150804 150047
157978 158916 158142 157645
160215 159417 159830 160088
153739 153290 153521 152714
133064 132856 132905 132618
98163 98488 98234 97723
52978 53122 53194 53089
20014 20681 20782 19981
8641 8639 9003 8470
6465 6303 5970 6243
5437 5791 6541 5353
3686 3850 3721 3980
2779 2198 2189 2791
130 132 94 79
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
