A = [
672301 936170 12582202 454309 469915 451080 433748 443812 423798 414940 409119 396824 401179 392214 384328 387135 375357 376009 377144 367323 362845 361774 359373 356259 355911 356688 357106 354381 353871 350086 349778 351295 347912 344236 344768 346999 343289 340769 340797 342955 339616 343086 344586 344609 348552 346406 343563 346335 344902 341490 338299 333742 334477 334604 328989 329267 328425 329659 326939 321978 321645 319624 316996 311370 309474 307258 302481 299861 296268 293810 292344 293138 291689 290857 291363 289682 287963 287242 283605 280307 279172 277588 273501 270998 269257 267294 260580 251782 248331 245621 243796 241711 240458 239256 237014 236350 233500 233654 232549 230015 229110 227521 226462 224102 222820 221762 221125 219670 218324 218014 215980 215085 213975 213367 211836 210488 209177 207898 207280 206655 203789 203459 201178 200381 198365 197021 196023 194398 193338 191790 190681 189387 187834 187080 185109 184511 181977 181992 180315 178189 177200 176059 175376 172772 171156 170251 169123 168081 166046 165048 162980 161436 160780 158705 157603 155927 154386 153434 152318 150444 149246 148508 146737 145620 143638 142234 141464 140498 138940 137016 136376 135145 134028 133352 132488 130901 129822 128584 127181 125739 125013 124552 122492 121958 120474 119369 118407 117603 116826 115423 113862 113257 112088 111147 109799 108502 107794 106421 105370 105159 104014 102688 101890 101325 99719 99498 98317 97235 95745 94332 93946 92456 91634 91126 89857 89336 88187 87611 86699 85557 85176 84299 82965 82170 80450 79216 77952 77442 75782 74369 73392 73185 71687 70774 70450 68528 68390 67478 66407 65721 64564 63704 63202 62309 61751 61062 60153 59562 58654 58381 56960 56672 55338 55314 54544 53774 53013 52827 51706 51165 50167 49298 49252 48424 47673 46958 46373 46082 45613 44349 44179 44041 43301 42360 42075 41491 40973 40386 39794 39188 38944 38350 38335 37445 36941 36644 35712 35394 34943 34287 34474 33331 32704 32575 31938 31853 31207 30507 30073 29537 29395 28942 28506 28173 27451 27218 26718 26278 25971 25805 25325 24709 24724 24282 23653 23357 23287 22618 22477 22355 21898 21657 21438 21025 20544 20300 20129 19850 19225 18996 18843 18703 18184 17986 17702 17304 17214 16667 16777 16281 16037 15784 15390 15259 15155 14754 14620 14402 14259 13812 13429 13532 13368 13027 12778 12767 12330 12326 11989 11883 11597 11584 11391 10948 10988 10742 10649 10405 10156 10001 9816 9754 9712 9460 9312 9099 8916 8899 9027 8523 8403 8394 8238 7939 7732 7738 7549 7535 7402 7140 7106 6967 6987 6798 6683 6365 6375 6233 6281 6067 6056 5886 5840 5981 5633 5571 5498 5417 5375 5196 5026 4973 4910 4780 4764 4692 4711 4590 4360 4425 4307 4246 4133 4193 4183 4090 4013 3782 3861 3718 3648 3521 3542 3579 3422 3251 3315 3281 3177 3211 3068 2966 3112 2921 2925 2918 2865 2774 2725 2742 2669 2631 2715 2581 2411 2428 2349 2382 2387 2357 2324 2263 2211 2110 2177 2059 2057 2018 2083 1998 1934 1953 1876 1830 1831 1769 1745 1751 1723 1633 1596 1649 1607 1691 1484 1546 1528 1431 1411 1513 1413 1405 1374 1343 1339 1316 1380 1279 1275 1248 1207 1198 1217 1179 1123 1177 1122 1106 1108 1091 1126 1054 1000 982 1008 1053 989 937 962 921 902 885 932 898 895 865 871 856 824 812 852 803 833 787 750 765 750 784 720 728 768 716 729 702 685 689 666 693 697 660 652 648 704 598 608 638 615 615 572 626 583 611 591 532 569 531 591 558 571 581 522 527 496 526 474 536 500 464 491 471 475 448 461 449 479 474 450 482 449 431 435 443 434 431 453 438 457 403 445 408 425 416 365 365 408 408 387 396 327 391 409 404 383 340 366 378 340 365 377 349 355 326 339 356 312 354 336 321 336 316 301 297 293 271 301 307 313 292 344 285 272 323 292 252 285 285 307 323 343 324 306 269 278 272 319 272 272 284 306 300 291 265 265 257 268 282 288 294 272 242 283 295 291 286 300 252 266 280 273 269 275 266 249 299 312 280 298 270 282 289 252 244 267 267 260 251 257 268 227 259 217 248 217 242 250 247 211 230 219 207 218 218 227 213 210 240 195 206 215 181 180 203 206 200 213 192 196 192 185 202 179 180 179 220 210 208 217 199 197 203 174 212 208 219 182 219 197 202 235 192 220 190 216 217 202 232 202 211 236 201 207 193 193 192 216 224 182 198 182 169 201 201 183 165 186 198 177 177 159 185 159 188 187 165 180 175 172 172 171 183 174 160 149 153 159 134 165 176 144 156 140 152 191 163 166 146 151 138 150 166 180 156 141 144 154 153 148 141 133 120 122 164 161 150 140 122 136 136 114 145 144 134 151 139 150 140 165 124 149 129 130 139 136 136 144 131 145 120 138 159 144 166 130 131 144 155 145 150 109 153 157 146 146 152 146 147 146 147 139 142 138 140 148 137 143 146 133 128 128 129 122 114 151 119 131 130 112 123 135 135 99 119 140 134 152 142 132 123 126 134 117 96 129 105 136 107 125 106 125 117 151 137 114 134 107 131 126 108 111 149 126 117 129 113 103 131 137 136 114 129 126 121 114 126 100 150 127 114 126 143 127 129 114 141 130 127 121 119 119 126 106 124 97 141 128 123 105 103 109 102 111 130 119 127 101 125 145 134 130 145 134 127 127 135 125 117 117 110 128 112 107 109 96 99 134 90 112 91 96 96 93 94 99 96 91 104 86 107 101 101 106 73 101 120 112 115 86 96 106 88 96 79 100 99 109 119 95 110 95 94 104 90 90 102 94 90 76 95 87 113 83 82 71 62 87 91 80 96 91 87 75 73 96 73 88 59 68 81 77 76 69 69 72 66 74 71 71 73 64 69 67 60 56 73 54 84 58 53 78 75 66 66 55 88 88 67 87 79 69 73 94 117 93 92 88 97 102 109 87 87 79 85 95 80 86 77 68 65 76 77 75 85 69 84 68 78 90 78 84 52 54 40 71 69 53 59 59 80 67 52 53 60 48 57 73 71 94 117 123 168 166 179 162 201 212 194 177 188 206 192 144 145 152 169 132 171 155 146 144 156 143 158 162 164 183 205 187 287 187 169 184 191 197 179 131 158 142 146 151 144 135 144 134 157 153 123 135 137 115 103 97 74 48 55 243 46 69 55 48 144 54 57 48 46 60 66 61 57 48 41 50 36 56 51 46 46 66 54 72 72 77 81 78 88 76 95 80 100 108 102 103 117 112 100 129 126 117 137 120 158 157 190 193 155 200 211 223 246 231 220 222 237 214 250 249 233 231 257 289 243 220 184 139 108 110 77 80 67 49 47 50 40 40 53 34 34 32 47 38 43 44 49 45 43 47 43 42 42 43 51 50 44 40 39 44 44 39 54 38 43 46 41 51 45 43 40 52 31 55 50 41 40 44 35 53 48 50 38 51 38 39 50 43 38 42 47 52 45 37 44 42 34 35 44 48 46 42 39 37 52 42 47 44 43 43 42 42 42 50 50 47 45 52 35 36 41 46 38 50 37 33 37 27 25 37 41 20 22 27 25 39 35 30 40 33 23 32 29 36 26 32 26 29 47 51 30 40 32 51 43 37 43 45 39 30 37 35 39 38 36 30 31 41 35 42 40 34 34 34 42 40 41 46 40 42 50 45 50 30 28 25 29 45 87 67 27 35 46 32 46 46 44 40 55 54 52 53 48 53 54 42 61 66 66 54 57 45 47 36 28 42 42 44 47 42 41 47 43 33 52 57 36 47 56 54 49 53 45 45 41 52 49 52 52 48 35 45 59 60 60 46 44 35 48 46 63 39 45 44 46 41 44 44 55 50 57 51 42 61 56 63 43 41 40 36 35 29 26 29 30 23 23 34 41 36 29 35 35 36 34 41 52 42 33 28 53 59 45 32 36 46 42 43 44 37 41 57 44 37 50 50 53 47 36 36 46 39 56 42 40 39 41 43 44 51 41 38 42 44 57 31 36 47 47 42 49 56 50 74 87 57 68 80 69 77 81 67 72 64 58 59 58 53 50 45 50 39 39 43 32 41 40 31 31 36 45 48 34 41 39 43 36 45 49 47 41 32 31 34 37 24 29 40 33 27 23 37 22 19 21 17 19 24 23 26 17 25 27 16 21 23 40 32 30 36 26 27 27 37 25 24 27 31 25 26 31 18 27 27 24 26 28 22 29 28 23 28 29 17 19 16 24 13 25 20 31 24 16 18 27 26 14 28 17 17 24 34 25 26 38 24 18 26 21 30 22 29 27 23 26 25 24 24 21 27 18 22 15 25 24 29 22 18 13 20 17 28 27 28 29 39 24 33 26 20 18 31 27 25 30 28 31 20 27 30 28 18 36 22 25 30 18 15 24 19 20 21 21 13 12 15 18 15 7 12 13 13 17 15 16 17 15 12 13 8 17 16 10 11 17 9 13 13 18 12 18 13 13 10 12 13 15 7 18 13 7 17 9 12 15 11 10 14 13 12 9 13 7 12 20 12 18 16 18 20 19 18 8 19 11 11 20 22 16 15 25 18 13 13 19 12 10 23 8 17 13 15 12 10 18 9 13 16 18 7 6 17 18 16 12 9 17 17 13 6 7 8 16 9 9 4 14 8 12 12 9 15 8 14 9 14 11 17 15 12 10 15 11 12 12 12 21 13 9 13 17 12 16 16 24 15 22 20 11 20 10 14 21 13 24 23 15 21 13 17 16 17 14 20 25 22 16 23 22 17 20 26 20 30 29 27 21 14 14 26 14 20 20 18 14 13 11 10 19 12 11 20 17 21 13 13 15 19 13 13 18 8 14 16 24 12 14 19 13 15 14 16 20 10 18 24 19 16 14 16 19 17 20 14 9 14 16 16 20 20 21 16 12 12 25 26 25 29 24 23 20 21 22 23 21 18 16 19 17 13 13 19 12 14 21 12 9 9 19 8 7 10 12 13 14 12 15 13 22 13 18 12 13 15 21 9 17 19 13 16 12 11 12 20 21 
];
B = [
0 0 0
 202822 144120 58702
 242872 189290 53582
 212531 165799 46732
 358027 306593 51434
 141514 111750 29764
 610317 556306 54011
 217811 193448 24363
 79534 64170 15364
 191097 174775 16322
 59796 49666 10130
 31803 24962 6841
 24902 19942 4960
 34351 29471 4880
 255057 242492 12565
 245141 233228 11913
 128981 119518 9463
 734370 707448 26922
 173246 162354 10892
 313509 300721 12788
 113569 106319 7250
 332733 320179 12554
 323373 311741 11632
 114043 107611 6432
 320493 309443 11050
 116669 110754 5915
 556618 539308 17310
 335921 324868 11053
 111485 106317 5168
 339576 328924 10652
 110756 105858 4898
 339875 329707 10168
 328175 318567 9608
 117596 112930 4666
 415287 403066 12221
 126503 121663 4840
 329838 320421 9417
 118391 112024 6367
 325557 316525 9032
 326163 316894 9269
 131195 125335 5860
 315561 306716 8845
 125881 120606 5275
 338204 329203 9001
 303136 294861 8275
 116902 111828 5074
 309401 301405 7996
 126731 121698 5033
 303172 295201 7971
 125099 120264 4835
 283742 276439 7303
 310289 301729 8560
 103462 99919 3543
 290054 282088 7966
 102280 99053 3227
 290582 282431 8151
 259550 252224 7326
 129385 125741 3644
 277061 269544 7517
 102625 99962 2663
 24408324 24055026 353298
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
63 60 0 1
34 8 0 0
47 25 0 0
40 17 1 0
33 23 1 0
27 20 2 1
529 45 15 1
3206 40 38 12
14707 44 178 30
62226 69 280 77
200792 82 326 120
598597 114 432 189
1458667 122 547 267
3054195 206 663 382
4944698 272 740 509
6664084 353 804 624
7378843 488 890 785
6455980 641 916 917
3858839 785 1035 1069
1387691 930 1282 1306
259522 1115 1428 1452
21469 1403 1638 1759
2998 1720 1922 1956
2746 1954 2134 2227
2875 2238 2425 2340
3131 2652 2495 2502
3255 3074 2807 2842
3751 3734 3073 3076
3937 3850 3163 3452
4062 3825 3384 3730
5937 5331 3637 3654
4843 4680 3700 3685
4731 4505 3841 3964
4279 4310 3657 3687
4525 4968 3813 3669
4619 4980 3642 3798
4046 8476 3604 4039
4010 3873 3462 3566
3988 4085 3447 3541
3739 3733 3566 3510
4172 4027 3542 3598
3945 3980 3752 3756
4888 4776 4597 4615
4014 4137 3991 4071
5255 4989 4169 4103
4867 4647 4144 4259
4385 4354 4286 4136
4144 4330 4190 4295
4126 4032 4258 4349
3942 4114 4152 4193
3904 3873 4096 4253
3466 3483 3818 3876
3314 3436 3375 3506
2941 2854 3102 3179
2570 2543 2671 2704
2228 2364 2313 2424
2100 2014 2231 2397
1934 1867 2193 2337
1590 1628 1900 1870
1638 1507 1858 1862
1476 1449 1544 1455
1476 1430 1479 1482
1322 1422 1563 1565
1448 1472 1551 1486
1411 1462 1555 1658
1558 1412 1397 1395
1453 1389 1492 1486
4654 4506 2889 3413
1755 1797 1864 1800
1893 1888 1939 1859
2433 2406 2475 2432
2258 2306 2882 2823
2436 2454 2403 2370
2482 2483 2527 2581
2498 2464 2393 2455
2530 2491 2367 2345
2037 2033 2105 1993
1728 1745 1603 1654
1469 1490 1520 1461
1173 1154 1134 1124
776 736 759 737
469 457 537 476
23 23 30 23
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
