Mastot

"""
7
2 1 3 3 2 4 1
1 1 1 1 1 1
> 2

7
2 1 3 3 2 4 1
9 5 7 4 7 1
> 10

4
2 2 1 1
9 5 7
> 12

2
1 2
5
> 5

3
2 2 1
3 2
> 2

20
1 5 3 7 5 6 4 5 2 3 4 5 6 8 3 1 4 2 5 1
195 621 7 351 486 13 648 312 64 123 48 12 65 153 846 5132 651 165 324
> 343

20
19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 1
195 621 7 351 486 13 648 312 64 123 48 12 65 153 846 5132 651 165 324
> 324

5000
2485 221 2889 3469 3198 476 355 299 1954 4461 2393 908 4065 4810 2367 1122 3374 4513 4686 3910 437 249 336 1604 3228 4645 4846 1368 1195 4747 2210 3988 3547 3140 3561 3919 624 1881 635 1549 839 4597 2562 1074 3928 2219 25 37 957 2699 4996 1724 2879 1796 4472 2792 4913 1056 952 1879 1732 4138 1705 1585 1765 1222 4594 2154 2787 901 4649 2605 3948 1659 4033 990 921 4498 2070 552 3667 1816 2428 4092 2318 292 1463 4550 1752 2920 2304 1246 3592 690 2664 2940 3474 2857 4944 1922 849 503 1732 62 3561 4839 3248 3483 1392 2716 3164 2638 2 3008 2703 2503 1459 58 782 2924 1130 4021 16 4131 3127 2416 1327 2128 1208 570 205 671 4813 1750 843 4837 2047 77 4950 4769 766 2276 1149 3341 643 4991 707 1793 3228 914 3208 4226 1627 4847 1483 2228 3140 3820 3733 3940 4612 3354 2576 4168 4605 4832 3829 2021 18 4983 3394 1683 1137 3279 776 3210 2569 2852 4544 928 1510 4989 4180 1189 3130 676 4569 374 2454 3674 2534 3459 2977 784 3321 2392 3884 4152 2193 3316 2291 3282 3191 3462 4689 1882 1860 262 2597 956 1502 1812 2326 3002 1357 4517 4036 3641 4884 69 2489 2598 4785 4469 2395 2089 4050 3156 4130 2532 2968 795 90 2032 258 2067 3178 4235 498 1134 2786 3431 3657 2911 2448 3010 749 1387 1098 4157 3145 1377 3683 3422 3430 4670 4966 3441 2689 1432 4690 3692 11 4426 2771 3369 2142 3212 2955 1823 294 4679 165 1656 2382 4463 2854 587 3523 1963 1656 3035 3238 3609 492 4567 3664 4016 3571 1064 483 4545 4373 2820 986 2824 3804 1352 1676 2505 2372 1153 493 213 3949 294 2676 1666 3255 4732 1308 75 3696 528 3423 4304 3530 3568 299 1627 2346 1363 2676 884 2106 4225 142 2794 1530 4043 1080 3360 2928 547 1877 1175 4083 852 4768 1287 2268 864 1206 1166 527 1916 3303 74 1946 2996 1681 4641 2988 1511 3431 4533 601 2256 8 513 3303 4490 4164 261 4341 875 2704 865 4482 4299 3144 1394 4564 571 3895 2986 3970 4348 4963 318 4587 910 3573 3378 3792 1097 259 4961 4362 542 2359 1417 2055 3974 689 3926 2881 4373 2085 2878 348 2162 247 4204 2046 390 1960 32 168 2088 800 4301 3052 86 2397 4504 4188 4241 3541 593 4645 2218 4594 3187 1721 2953 2284 2277 4750 4275 3322 3543 2757 1363 4085 3117 2464 4141 799 4407 3858 3025 4273 2381 2674 2604 3985 1049 4861 3615 3871 3034 886 3205 3383 1105 3844 2162 3115 3 2725 1358 1625 732 3761 3551 1560 4640 4291 2763 964 3780 1913 811 1500 1518 1275 1762 3654 3057 474 2042 120 1900 3195 4003 3652 4507 2594 3827 4627 1827 3366 3504 1302 4416 973 3539 659 2405 1667 3850 2657 2635 3561 4657 2341 1153 4826 1346 484 4808 38 3684 3550 2421 2543 1319 630 4925 3396 4933 4948 4923 3646 1019 1378 139 2228 3442 553 3961 1136 4561 2144 1449 3011 4301 3594 2009 2689 1103 3021 2121 329 4902 3681 2552 4236 3251 3794 2429 3650 980 3604 4446 2995 3024 468 4448 36 4435 2952 4722 2558 2657 3197 3237 2880 2581 2591 2753 683 1745 2487 293 3480 3883 3380 667 2517 2234 1937 15 1996 4127 3821 2060 4622 494 1704 2168 1769 1674 2440 989 3722 1828 1520 1279 428 2582 4308 1300 1232 1798 1156 913 909 4437 931 4676 2286 839 3214 1634 4992 3656 4691 3393 4978 2611 2257 346 3911 1820 3631 2270 2638 3093 1562 3699 2202 1092 4863 4020 3606 2125 3775 2062 1420 1283 2304 2142 812 4697 3713 325 779 4790 2097 2690 4394 4064 396 1365 449 855 2672 637 361 3732 2933 879 3724 4156 1122 2462 3774 4060 3228 4180 2914 1636 977 439 3142 4797 4694 720 4590 1163 1435 3913 3017 4819 74 1651 2687 1116 2437 4245 3202 2164 3609 294 2653 4222 4088 2144 4770 2214 3966 2617 676 4883 2396 2904 1394 2296 4520 2159 1742 604 2784 4145 1504 4370 818 661 3414 228 223 2725 3203 195 2144 4467 3755 4229 4674 1586 3096 2985 1941 2523 829 4501 2033 2501 786 3674 157 1243 4077 3399 3141 2192 4726 4161 2224 3058 2296 899 1229 3615 3764 1004 3872 1113 1429 26 1714 2615 4009 83 2392 3816 3322 4712 2579 15 3342 4996 1146 767 36 3125 3131 4246 2839 4942 2427 3134 2911 1501 2111 4799 3814 396 476 609 172 105 1170 2613 308 2050 3615 1666 3376 1607 1178 3395 2509 3076 3381 3559 4077 3284 4350 3826 2415 4347 119 4756 534 3865 544 144 1872 1013 2409 861 2287 3342 2344 2934 4640 3861 3124 3384 3977 1454 3073 1151 1467 3643 2116 2375 4468 4879 4834 3751 2380 1270 916 3163 1343 4969 3295 4863 3695 4942 524 3809 2633 326 155 1767 369 4938 4539 2853 1339 1026 858 1086 1317 1624 2287 2147 3563 1280 4651 821 4753 2789 4765 4950 3400 719 3434 2567 1865 3354 2145 4109 489 3972 680 4291 1634 2947 595 2105 1298 4395 2740 503 2702 2792 2143 173 3797 4693 1910 2780 2420 4379 887 1272 1341 163 3772 1422 320 1924 3441 4656 3211 910 4474 2749 2716 4329 2995 47 2001 723 1397 3582 3580 1239 2308 4763 4676 1925 2500 3532 3646 3440 215 2685 1707 4558 877 2979 4262 1001 2289 4488 4239 3521 4473 1320 4975 3139 4166 1836 4714 2138 920 3446 237 4668 3156 4899 565 1890 3901 657 1525 1540 4680 436 895 1814 590 2896 1968 18 3429 4339 3851 3867 1860 1500 4409 1903 968 3819 1619 996 428 1630 2015 4161 4107 4555 3153 3334 2536 4888 2232 4804 4545 1996 1688 3871 13 389 1264 2045 2098 3261 198 1328 1718 4193 1370 4347 1745 1022 3274 3667 261 3523 3117 4987 4391 3255 3877 3334 348 3772 2110 1900 1742 979 12 1708 2462 2197 1186 3837 1512 4836 2893 4189 4337 1293 2051 3772 2734 3466 4094 488 219 4535 165 3758 2874 1572 3020 1411 346 2260 2048 4797 2062 276 3433 4909 4082 924 2708 3068 2956 4568 337 2356 614 2587 5 2116 4658 1558 1088 4300 4539 3210 2738 3232 2003 1567 3710 280 3228 1507 3257 43 2481 1875 3688 4467 2450 2406 178 1564 278 3985 752 3507 4991 4326 2431 1250 4776 2620 3801 1500 3229 1181 4374 482 2782 2287 4923 1635 3409 3898 3654 2408 2475 569 2654 2269 2369 4917 2708 3836 3626 3823 4610 868 1585 3688 288 4878 3598 1134 3643 1556 1594 2457 1811 4018 4956 37 3052 873 1758 2110 1354 3012 1677 1894 1283 4621 3097 3673 3679 4409 4145 4473 4166 4832 2550 4558 4506 4516 2072 1496 164 651 3031 4109 4652 1668 1483 1821 519 528 4149 2457 4853 3274 4678 3324 74 2164 2536 1476 1567 2580 2075 3581 2878 3067 553 1585 3675 4897 1522 3319 1048 3014 1671 2076 4371 2884 4767 684 3135 1748 2356 2368 201 1030 4159 2110 1725 3214 675 237 548 4344 2982 4082 5 1559 2354 2609 3532 2666 1154 848 1266 1701 821 2007 4302 2177 3060 2982 973 1326 2603 753 1136 1408 1611 1309 4099 193 1309 3111 533 3353 1776 2628 466 2943 4275 1054 1199 4739 863 3397 2278 3910 1545 3173 4559 475 2347 2987 3185 4818 2944 189 4589 3954 2108 312 2278 2324 4362 3309 2417 3880 3957 479 4260 3275 1862 3640 3460 4985 4143 1003 3152 126 3592 4232 1477 1133 4271 1932 4019 2123 1164 3341 2124 485 577 66 3963 1369 1627 4139 448 3001 1396 1900 4925 316 2033 1342 2283 3573 3890 3522 64 611 1610 3688 2637 1320 3611 1388 3360 2455 2850 1737 2101 1672 1423 654 2496 2847 850 2074 3657 4839 2216 4100 4094 1089 1050 4075 1609 1599 931 660 1833 4165 1704 4202 629 3181 2389 582 2216 2537 836 4372 181 3154 3806 2254 3163 674 2577 1957 2213 3454 1715 2327 4983 658 4762 822 4660 3642 3049 3764 4313 1062 998 143 4506 4178 987 1231 3343 3365 448 4932 4844 3696 1086 1747 2242 4615 2764 2081 3819 2878 2598 3287 830 4090 1398 687 1216 3237 4196 3816 896 3032 1919 300 1328 1337 1357 1291 4866 2115 2353 590 2150 1562 1347 1664 2043 4419 3752 3476 1569 3468 4142 837 289 898 1997 315 794 4479 1003 4605 4786 3027 453 3244 3630 2666 146 3961 675 3777 4983 3726 916 2662 2542 1313 4392 319 2803 4845 3525 1794 1062 1652 3131 233 2611 90 4293 4769 3325 4039 798 4493 2218 2669 4000 1653 2085 1916 4352 602 570 2206 1312 1850 2555 4259 4394 49 3387 352 3362 1563 102 907 2547 1973 1673 819 1600 4088 2294 4211 744 4038 4314 1517 1886 719 4812 40 1352 1478 4236 2054 4729 3320 2302 1271 2147 1366 1849 3833 1853 1178 3496 1696 1862 1498 4340 1359 4258 3842 405 4565 2490 4002 1574 4004 712 1090 143 4439 2728 1034 1001 1349 2759 125 3728 4175 3454 3207 2119 4470 1657 4415 137 2634 1167 3266 1938 344 1074 3856 1712 1972 2235 4418 4678 1397 4419 2309 2546 1973 1893 1958 112 718 3959 495 92 50 3983 251 3810 2652 4673 3511 1343 73 3416 3376 4787 2851 1695 2137 3060 2153 1040 4895 4484 1696 2171 4625 201 3798 2559 1764 4564 1865 2023 2992 4562 1996 2429 2013 1794 3526 3425 900 1625 2421 3084 2408 4102 2706 517 63 2076 2116 2275 4099 95 3645 1616 4784 557 4685 695 4532 1595 1518 4169 756 4030 361 1150 1939 1550 3795 2531 622 3846 3331 3924 2380 2550 4301 1727 1579 4868 1718 2384 1782 1266 2333 1902 991 3131 4542 4596 644 2200 1851 2724 2803 1647 2867 29 1842 3059 1290 2458 4188 2277 2774 2848 4545 2620 659 4952 1695 4382 4879 2076 549 1677 3731 2672 3608 4829 390 591 3917 2573 1612 4211 2116 290 735 388 4040 3953 3540 2907 3490 810 2266 294 2961 1998 1368 4136 749 664 4532 52 4609 3659 4482 1731 2304 3281 31 1424 4990 4871 145 1995 253 3475 459 4542 2386 2412 3769 4223 527 2074 4596 2346 1089 395 4781 1694 761 314 3066 1736 3756 3288 3859 4157 4953 4223 930 3847 4454 976 450 1410 4182 2749 4950 3198 2197 993 4735 3204 2017 3834 2076 908 3262 4125 2956 2975 2512 618 2968 2714 967 2864 2505 4046 2167 3133 1846 3759 619 709 3886 2168 1535 2670 4277 1101 4154 2135 2735 1006 2381 2087 2855 2033 4545 2771 1459 1131 239 2228 3040 4812 3853 4407 3857 453 1419 1298 3444 2855 4429 1154 2335 3109 3213 1025 2617 3161 4095 2613 1889 1253 62 1786 1470 4848 954 1918 2897 66 384 3444 4825 227 523 303 920 1470 1220 1094 3498 132 4950 3175 4058 193 2118 177 4270 4202 2534 1989 4911 2520 1064 2649 3624 1382 1480 3558 3106 22 882 1276 783 162 4686 3911 4618 370 2616 2663 2991 1358 2372 2798 709 787 4944 316 2339 3027 4443 472 3435 2497 3437 1608 1519 4837 1544 2756 3740 1287 1231 3903 3319 4439 2748 4378 3950 13 2855 2967 4421 670 1392 3927 3577 4130 2750 4698 4983 3468 3417 1872 3825 4494 493 1382 3028 1397 360 573 2406 1529 3125 4197 893 813 4525 632 3795 1026 1489 2577 1610 2153 2242 4684 3035 1970 426 3718 3855 2570 2010 3103 2379 171 1853 3548 1483 3568 1376 987 3125 462 3084 1795 3366 4376 2507 2680 3393 1824 333 1241 3886 3485 3518 3187 3189 799 3426 2332 3962 2437 4369 1709 4741 377 3338 1719 2330 2058 3171 1043 2490 3640 4192 1081 3867 3889 1595 3870 1509 1775 4774 1606 1775 4090 2889 3576 3643 3737 3590 1590 4395 1793 740 2531 684 4444 2672 3351 3315 2766 582 1146 2314 2619 1146 1122 1481 4957 754 1183 2844 1794 742 1655 2900 290 671 662 3067 3070 1713 4355 4259 571 4687 2080 4031 2256 4585 204 1100 3353 4699 4228 231 2622 2903 203 3192 3902 1956 3895 2652 2302 1723 1880 2458 300 1330 2971 1933 4270 4269 1701 4078 1204 1579 4740 1922 4344 2482 4063 472 2326 3028 1964 956 2750 784 3940 4904 898 3039 1595 3622 4095 3227 4204 4154 1575 2367 2972 4502 3729 2965 1617 1771 4195 4580 735 3756 2473 925 4063 3251 480 1377 2021 928 2767 2004 867 3906 497 3957 3872 4424 4077 4106 2426 2713 4989 4255 4675 4451 1133 655 99 4173 1017 833 933 4211 4658 3740 4098 1195 4721 1227 3560 2968 4847 284 1270 3827 3545 1042 4250 1286 2964 345 2237 2190 3705 3209 3976 4106 2286 786 4071 650 2326 4875 3163 3875 900 2449 2352 2442 4948 1596 4631 1581 1773 1169 4316 2898 1905 298 1205 1835 2098 3372 3896 4365 839 1504 3221 2313 3671 507 4546 505 2810 4571 3909 1778 3908 564 63 3766 3065 2079 1998 3406 258 4888 4376 1511 3832 2988 844 3536 1886 3561 4828 4087 1051 4109 1518 491 558 1656 554 4451 2870 4034 3385 2262 3704 2461 2862 4790 2639 3625 2320 1953 3721 3555 1495 4620 2309 4684 1490 3279 4819 1380 764 3172 2146 4037 4562 1559 3278 1743 537 3799 4344 2245 4342 1726 4461 1616 977 1018 2738 1712 2219 827 1935 435 3482 1013 1786 2824 4031 693 2260 4251 4536 3768 1720 342 1579 1973 4875 528 3472 3999 3349 543 4879 405 723 1402 2054 2313 4301 1162 1841 305 863 3395 3392 148 2003 2545 2987 6 1115 1263 911 2254 3597 2305 1507 233 4711 4557 4648 806 2120 3161 291 2960 4169 3447 469 695 1537 174 3439 823 287 2087 1106 4883 2536 2804 1690 4750 3354 1489 3769 1158 122 4642 3895 667 4779 3518 829 3661 4116 341 3340 2820 2774 2600 3488 4555 3318 1725 1729 4420 1247 1439 3431 4615 3671 4528 3445 728 3253 2860 3611 1533 2719 3565 1032 586 243 725 2336 3625 2387 2966 1326 1615 1826 1975 308 2165 3844 4334 1097 4465 631 3296 1254 1452 3328 1286 202 3132 293 112 2674 360 3541 80 3535 1735 2875 114 4733 2947 2560 1386 3542 4771 1855 2958 3965 4826 4733 926 1846 4005 2897 3819 894 4721 432 1751 3678 224 2050 159 199 3470 232 4078 4766 2385 3527 2175 2294 13 2275 3029 2023 1301 1594 326 3314 4137 3164 1759 4059 63 2060 222 330 3121 1814 1737 3451 2640 2536 867 3846 4063 1551 1997 3773 4156 1562 297 2881 205 4537 2997 1012 151 797 1120 1332 4125 3682 4876 2630 481 1822 2527 2496 1085 3018 4243 731 4212 384 3920 3672 855 2233 202 1875 2105 1113 244 174 4132 2285 377 855 1583 1683 524 2961 4044 4011 769 3702 1412 1521 2566 128 3914 4191 1366 371 4332 980 4790 1524 3927 1818 4841 2334 2830 146 4778 2485 3597 876 358 1251 3372 1387 3527 2590 1520 1747 708 1298 1437 1595 3750 1660 4004 4017 85 874 2713 4660 3276 4853 4834 3340 2422 3692 2490 1593 2822 2314 3888 2688 400 4050 1411 3543 1502 4781 4170 115 4350 690 2350 164 3683 1762 1472 783 949 1754 2310 632 822 4859 857 1381 3810 30 1417 4440 3300 257 572 2098 4774 4270 66 2131 2668 4027 293 4736 2350 3428 2431 379 1383 4399 1198 2252 4042 1533 1233 4779 4921 1869 2250 1521 3105 3173 4706 4587 367 3543 1769 2607 443 4472 2128 4606 1586 3689 4111 1202 877 2450 249 4303 2135 2584 4341 1914 3909 1790 4448 4752 3812 635 1767 2881 3092 2953 712 2675 3322 3804 1461 3771 2053 2093 2854 1320 4866 991 1669 2264 3808 1376 4038 2005 2435 2811 4097 233 481 825 4636 794 1413 4935 1113 3348 4306 4152 4455 353 1026 840 4648 3078 4272 4183 717 2392 580 2397 3746 2694 3573 886 563 2784 4505 711 1459 3080 2922 1292 1992 3807 2635 335 2206 4741 1147 4909 66 1830 173 3486 1032 1895 152 1266 1631 1072 1315 2047 2391 4493 1721 170 1484 4638 3095 762 3 277 2644 1006 4884 269 4275 3227 172 2278 1806 902 2909 3701 4588 4061 2423 4803 2976 4975 282 2786 2910 342 3020 928 686 4052 4595 2165 1362 959 1190 3916 148 1872 2052 1798 3443 4197 186 345 3408 3534 4159 3125 2411 4956 3489 4826 4726 3921 1691 3637 3435 1789 2984 3900 4975 2676 2123 3025 2462 643 3488 1677 676 3362 1214 1173 4414 1660 3570 4199 1122 328 2024 1638 2329 4873 2067 4626 3680 4945 3206 463 1399 3621 2180 16 324 3396 2731 4645 997 3223 2680 2846 2312 3749 3760 3189 594 4174 1125 4339 3984 1879 3108 140 268 4262 767 2674 4299 4136 248 218 2623 1655 1564 4267 4284 3430 902 3743 1975 1670 1945 126 3083 30 2211 761 2371 3203 2102 2154 2400 945 3116 3310 2214 1054 3687 4485 2017 487 3668 33 2455 2683 2496 4227 863 1375 3223 998 2206 3355 3369 623 2304 1440 588 2106 461 4777 2577 4021 1701 4281 1015 240 3706 4477 4421 3559 783 225 1397 434 459 2922 425 1200 1355 3365 3988 4826 344 2835 2169 3375 128 1684 937 556 4713 54 3192 2182 1694 3941 600 587 3888 4976 305 124 4638 2312 4662 508 1922 254 762 3343 4420 480 3041 491 1168 235 4689 1212 4360 3926 4048 1753 3315 4369 756 4902 4512 729 3381 1229 1669 1427 1313 826 2074 4376 2134 1566 2270 288 2339 4019 3875 2182 3855 3139 413 3004 4774 1961 1318 426 2889 3103 1215 2532 2187 2750 3715 1261 3845 4861 1173 2500 2391 1699 455 1875 2901 1831 4982 3879 2755 445 3285 4122 4424 1354 4319 4852 121 4518 131 4464 2433 1105 1165 775 2181 2280 4128 3147 1442 4095 4134 3327 3687 4005 3639 3732 2863 1834 68 1183 4252 4496 2026 91 760 1914 2979 2033 14 3550 3429 1897 4042 1993 2444 4594 2182 2190 245 4291 3393 275 224 2241 29 1504 1190 2046 1806 1772 3227 966 2158 1944 2954 2018 576 549 4892 3704 3108 1724 3604 465 2560 2160 1901 4460 4790 3607 4027 2071 582 2511 2471 4585 3729 4280 706 4823 1918 2137 2455 3115 752 1436 507 2360 1939 1591 745 1730 4984 4523 1320 687 3083 2381 4015 1820 2020 4854 1908 868 53 2618 1266 3808 1991 2956 3808 4474 3552 166 1273 1404 4622 2824 3940 1352 3174 4660 4365 1580 4027 2994 656 4968 1465 3774 178 3962 1376 885 2633 367 2320 4414 430 1538 3386 1049 4247 4710 1536 4251 897 4910 4054 96 518 3105 3835 4547 3689 520 2564 2438 3612 349 1540 3187 2743 233 3543 1012 1647 4614 50 1853 2371 1167 3879 409 4712 3647 2413 1183 3275 3147 2767 2378 965 802 3533 425 1915 3458 4471 3512 1198 1311 3762 2796 4085 1628 79 440 1710 1874 2115 4396 2435 1433 2796 1544 1640 100 4643 1416 3690 3559 2000 1427 1006 605 3888 4843 3607 676 4589 2092 4899 1686 3192 4671 4867 1105 2179 3645 1863 929 2946 2622 2937 1931 1813 3971 219 3335 1576 2434 3745 1563 407 4217 1589 3972 996 1808 4121 2902 4044 3823 2131 4668 4582 4110 4050 2836 4652 166 3683 1386 4431 446 2923 2232 823 3643 4499 2992 2253 1654 4758 3572 3476 1211 4957 500 2397 1921 1604 35 2585 2556 1328 676 2104 1057 581 1043 2683 2728 1411 567 1279 937 1301 3768 545 1300 2708 393 4925 2030 4946 1522 3277 3863 4197 826 3790 2826 4357 515 2975 3244 1085 4565 4102 3317 4148 4726 3924 2661 1660 1978 1774 1509 129 1227 1939 2161 4900 1407 2012 4679 4695 4071 2959 817 4228 674 3262 3412 19 3001 83 3523 618 1269 2234 1161 3604 2062 1201 34 4032 2879 554 3111 1711 2286 4749 3529 4895 753 4890 580 2358 1236 4131 4816 2879 3242 4368 972 2917 191 2603 1528 1170 807 2065 2138 186 3327 4074 3008 2417 4553 2489 4078 1674 1295 4076 3809 257 354 2869 847 1607 2507 358 238 3611 3350 2506 769 1346 3213 546 2691 2166 668 801 2568 4837 2136 1778 800 3255 3512 4268 257 129 3133 3578 1773 2379 3391 927 1800 4504 4014 1607 1183 1662 2134 62 4261 4402 2147 1338 3237 1426 2131 118 1974 2502 4535 3007 2257 2508 2850 3582 2370 1720 2099 3842 2789 1123 760 4346 1259 2665 2391 4806 4414 3111 2535 2402 3112 3753 3289 1412 1277 839 588 2109 2255 2154 1628 1150 1631 2913 3823 648 3720 4845 328 3211 1303 1290 1464 4636 3489 118 3617 2204 1961 3135 2747 3932 1140 328 3075 3526 3466 1314 3252 3161 2261 1181 2159 2275 119 4928 2781 3167 4849 1486 3802 333 2551 150 997 2325 1300 3708 2117 3377 2441 3322 1522 1251 4555 2756 1032 2979 4218 2413 4152 2903 449 2258 64 2065 3022 1449 1669 2249 4084 2046 1621 915 929 3951 142 1612 2639 1626 3655 3129 2651 1069 1834 4062 4677 3558 4085 337 3013 260 4001 4253 1006 345 1818 1794 4014 1155 1406 1468 3750 2969 2070 3042 161 3807 1087 2420 4342 3806 3405 3489 3606 3101 3082 1159 1084 2255 2533 4474 2624 2263 3799 4849 4170 1521 719 1521 769 1231 1112 1747 2999 1899 2516 1609 4746 4721 624 1118 402 909 2965 2733 2271 3119 6 4889 1112 1995 1810 4031 3593 2810 1472 2646 4184 2205 3989 2509 610 4777 3574 1001 875 1150 410 35 4706 825 563 4207 364 4445 4492 1716 1492 1334 4091 3066 3301 4221 4936 2573 3738 1281 1168 1189 3930 2414 1789 1165 405 2711 3363 3377 3119 398 4746 296 410 3440 4718 3225 554 177 70 744 2552 1008 1594 4827 3473 3485 2710 646 2353 4675 3449 95 2046 257 3326 3662 4798 2591 141 3840 3194 2537 3938 4707 3367 1310 3208 4275 4566 4402 2642 838 2675 1112 2263 3173 1068 526 279 4129 3529 1297 2516 3780 4858 2871 4931 1975 870 4728 1368 10 4231 3297 103 1844 4709 889 3023 1844 3095 32 2406 2150 1177 362 637 2444 847 4631 2693 4433 2314 2975 583 1888 1966 3572 4082 3126 797 4021 1258 4012 3058 4587 4687 2498 826 2030 2908 2002 4897 3630 1266 4707 4755 4370 3351 2002 404 1304 331 2668 2607 13 2587 4243 3715 3517 3284 612 3942 2545 4358 1441 4939 4583 3048 2045 109 3540 3989 4085 2929 4233 541 1250 4244 852 1601 1892 2094 1235 1142 785 4269 849 4614 4562 571 3992 4862 3973 929 4941 3843 549 2994 1557 1610 1204 243 1230 4026 3104 1793 4209 4350 1098 1010 1693 2492 592 4620 2818 696 797 2250 2267 3244 2227 2808 1390 1220 2461 2316 308 861 3056 2075 2792 4363 1559 2092 762 2435 972 3238 3294 1494 324 2586 1926 3006 74 3952 1108 843 3417 516 3049 952 4375 3801 2864 1683 1914 4302 4276 1424 3296 2011 4754 4442 1851 474 4656 2981 724 4917 3949 760 4428 4614 4842 3651 1253 2767 3376 4070 108 3598 699 1604 4537 2394 2960 4618 1276 1866 315 3960 4811 1495 4248 1173 4495 1409 1011 4701 1588 569 988 707 1218 4155 2084 2781 809 111 1718 2855 3961 1613 3680 3396 4816 3481 3468 4799 3061 2306 823 2948 1641 1845 1251 2490 4616 3363 1188 873 2562 3091 610 984 3712 1842 4509 2484 4434 2969 4888 4594 1683 398 4166 2795 202 1019 2897 2258 4986 403 1707 4907 3052 1559 3878 3467 3820 4326 2013 1226 87 4509 544 4770 1995 2420 2818 3751 282 2544 1453 112 4983 4396 4163 4863 3964 14 2865 1787 1306 2078 279 2527 3954 3576 485 2281 37 4429 133 4471 3258 871 2280 684 3341 2678 3384 2662 3432 4272 2185 4601 4090 1820 4025 3571 3039 1720 457 3349 3427 1962 1061 736 1205 785 4157 1399 2461 2762 2919 1331 3601 1280 1920 3318 89 3379 2131 4860 3379 2352 2328 1868 1359 74 2105 1656 4906 3190 3566 2453 458 4003 1138 483 1456 3391 2903 1815 4923 2594 2467 94 1246 808 442 1620 3783 4800 2844 775 287 98 3049 1448 3742 780 1990 3196 2414 1496 2995 2481 2124 1271 4922 1797 4910 48 3096 1316 3104 2807 3175 2726 490 4498 3946 1526 2596 1922 1196 3611 811 3869 4981 2986 304 3986 3708 3651 3131 2246 2155 2394 1623 815 3743 3988 3968 112 448 3340 4988 2432 2901 4537 4457 4164 1577 1351 4516 972 3978 4383 4563 443 3568 2657 1993 2552 4080 1705 4177 4732 587 3825 1998 2161 3129 4994 343 1540 3195 3532 4702 1868 4685 2793 2588 2410 836 3471 3903 3950 2049 1461 1111 364 4581 2798 1701 612 3667 3039 1787 2913 1121 4805 53 3386 2318 1189 2266 3476 2757 2695 1454 4863 1299 3096 3104 4674 1010 2075 3764 947 3646 2396 4111 3893 744 173 1875 4593 3458 245 675 1371 1400 734 2209 1882 1159 3509 2646 513 1263 1543 950 4268 1898 3195 2112 3236 736 492 267 3876 4253 4997 2972 1055 4933 2784 4805 4820 3527 1284 1569 4102 4120 4937 2821 199 2920 387 4646 407 4018 4425 3621 1673 1802 4346 4103 3946 1293 859 3863 3427 1665 770 1453 1587 727 4242 3774 4569 1685 4704 2430 4265 2570 1425 3905 1008 278 2534 1 3912 4656 1327 1479 2855 3799 3945 2268 222 1517 353 4876 2067 1674 2811 3414 1817 1333 4515 116 2607 881 1253 201 1554 2545 3313 82 2567 4750 4683 4714 4733 3194 2064 931 1531 1508 2885 1416 1337 2899 128 4859 3727 2810 3898 1847 1438 2138 2657 1206 2649 1170 2093 1350 1817 1278 2706 3498 1159 3115 4183 3517 1787 1693 1643 2493 981 4457 4782 538 3594 4786 4407 100 218 2765 4107 3314 1259 1042 3779 902 3274 3913 3274 1648 627 3150 1555 1196 1910 4009 2103 3715 2007 4464 3542 4046 1449 946 1076 3475 2917 3801 2081 624 3794 3004 2492 333 2443 566 187 274 1452 107 2965 741 404 1205 3531 3794 4121 2107 3337 3020 130 4420 2345 1980 2882 2853 1386 4678 1917 1381 515 4674 2930 3802 1787 413 1873 2801 806 4484 3705 2806 1114 4049 798 1985 2192 4119 3632 4784 1900 2736 4688 407 1162 4865 593 4215 2921 2046 3599 3009 4989 2629 2368 1270 4251 2603 3127 2310 4113 297 2051 2168 942 2131 2241 1448 4204 199 2121 3601 2532 1456 4408 3960 1063 1513 274 2986 1144 3582 4553 1407 4830 2586 667 2352 3088 2772 370 3415 816 2515 314 4777 2919 2860 1598 3606 398 4138 239 4273 4203 1525 834 4404 1330 1103 3384 3952 3634 1625 921 1363 2679 4797 3540 367 4339 604 1009 386 760 2198 4529 2505 4879 4720 3130 4616 4151 3276 2080 1594 1714 1376 876 949 3427 1361 492 52 3331 814 3007 4923 3658 947 1933 3602 2725 2070 2439 218 177 2796 2375 3955 2996 1539 2268 3611 1941 523 3438 1438 4365 1274 3120 1149 3625 4582 3861 1595 2813 1129 226 64 4030 2864 3326 2889 109 3013 3125 3421 4363 3667 3534 463 1462 1601 218 4283 3678 4890 3732 815 3436 3546 1583 1402 4041 4733 4862 1410 1163 4226 2155 4135 3811 139 1830 2100 4536 3297 2105 4729 1974 2646 2303 4344 2982 2910 4701 4196 3793 2021 1012 2860 2976 485 4251 1355 4241 3113 4345 4585 1787 3901 4092 1745 1542 390 257 2698 3136 2973 3670 2123 3827 925 2514 1364 758 3210 4146 2599 1404 2387 3506 712 4260 1087 1720 4418 4840 3736 226 1541 883 1640 4986 4787 3072 1023 4269 1486 1898 1201 4824 788 1243 4601 1817 167 3232 1090 1986 624 4866 4225 577 1417 3592 282 652 2292 1171 3781 230 3684 1673 1673 690 4125 4614 769 685 81 3204 3296 1551 3457 4939 2559 3811 2717 1598 4783 3532 2783 4598 438 4597 3770 3711 82 4221 3208 302 3189 3715 3798 3808 2580 3125 3827 823 3100 2424 3942 4676 4543 2709 4529 899 1341 3138 1504 3786 4277 757 1893 4059 3644 3086 2620 1075 4241 3251 2996 1793 3260 2686 2068 2494 2338 2126 1738 124 104 4464 4116 2106 3177 4280 243 2043 4697 333 583 1399 2052 207 1444 3863 3010 538 1783 3030 1072 3898 2854 3 4761 1507 936 2290 2049 937 887 1154 2113 2005 1441 3820 1063 2546 3419 4806 3026 3448 1995 2291 718 4648 4246 1825 1885 4281 1046 2713 3049 976 3362 833 3759 67 4411 1064 4798 1726 4441 2247 1355 4376 1294 2770 980 3980 432 1134 3164 3288 1054 1571 284 1446 1915 1749 402
899785941 367676483 574028531 909335865 225093730 622280165 656916808 93802717 690522257 15729424 662360295 851305834 783472023 539600718 672222801 863599075 211008715 321095591 638692492 67727157 70546284 999942981 264443097 969109667 327472765 858252233 526665422 450555150 951933444 612487446 85368759 613460089 162735041 774506993 663698232 720597263 980091789 359204128 188305401 768569954 602481996 98034973 991889525 224661055 457028945 867796582 104914955 960222585 283765539 815510850 386466590 255177612 380251392 37761068 524822868 967374111 998112946 444805587 312260920 454452602 902084446 154558733 488455207 866260217 906113156 84491907 379179026 120109740 461277949 880553538 218519075 559660228 36973273 356304603 984024243 263061777 526669604 162053297 910821946 957230831 985424771 475090221 816126357 929808284 837132474 587580967 370531465 971278722 79086116 517744884 131295543 247592073 797513334 461977391 649912161 194841926 326350638 937026447 758110143 264636451 329475987 765373675 6261581 68774290 418912786 685194427 727690667 24830362 248011786 760717941 83190549 978470992 96831359 692572792 536018025 496472707 792063857 416102903 890288198 436353091 853091669 447258372 660954638 390043880 79279161 873181787 481544574 265437207 194547541 307515565 913294868 222872982 932776322 514231099 747158602 667468988 443937894 2989058 362278499 939189934 131868117 938484056 451246244 70755783 710264084 138758407 681648102 461342202 108994246 33648873 657534 769610507 781609471 341380546 698722934 916643707 269160966 883688263 559752272 905348879 79902846 782462045 178673949 274991163 704159061 475570642 57943874 501095045 317862994 516751273 449580110 100770027 314024974 764032862 562467178 612745905 974766093 474133298 591538414 373932249 679247339 313204373 661198361 266312800 31918772 817541772 228002731 334953513 176503974 81615504 229869623 782557048 1327225 598383374 527173048 440970579 907080444 281255904 672753301 933944672 520158883 937327331 170110074 524583190 61106187 268474494 278015863 621915910 515489053 604313938 727508116 97300604 961450490 106549519 609435127 778501413 997179992 410058863 107336535 695683146 635019743 351000679 882314077 641003609 720368009 38959513 292520398 861836645 559096338 185638500 337533920 552791146 133444054 865578369 918665488 582145067 126921605 212636553 852832106 60798117 443311384 954148097 390486824 13975110 210540756 123727339 93662886 781443673 370751482 851740253 647452615 318478934 363001981 757442069 27290680 870424775 393427446 676521516 26731679 41265715 153517003 45180939 604784378 188557207 419304783 76434228 603596339 470527549 496295229 754330757 679402265 120484208 342261132 362849100 673129413 325735807 468571125 413400908 516829190 698591291 106131590 524137476 925115211 30871475 405061538 5060439 713482154 161313250 722112228 609503973 364593935 532508758 217851815 779636776 697227486 383814499 843005935 897699444 45406140 914696511 604621214 380428328 145464087 654909840 935660346 54906438 173089948 258426181 791044768 378209161 102710580 120043799 237747812 596745659 35864234 340387813 997830065 180469703 894130517 978221512 195563001 209409922 827799851 613249430 618654567 474371007 997176735 901028896 652743032 993479815 487562092 320146152 173061434 3386738 704841664 532968714 115959423 244252735 393207873 406355789 564792855 154502001 218718795 685623611 230852408 795012878 676402959 304881890 994690295 625966931 423893092 797603918 956442711 786396702 765749285 259094891 99820923 555594248 396730381 641722184 473927501 984185869 777743230 749624257 439604954 510066708 609404433 52934979 815656228 939145526 137035754 914913363 205783127 207985691 542846977 761956203 452076973 525927132 759783688 172429798 210772842 915566081 743589681 844629024 743458236 348870279 689496712 23094848 820857577 29496674 390420072 92050494 764680628 347474514 317746549 218296674 133810620 141065656 628556793 208216008 769248675 944287272 838621690 197907744 764051175 546358319 901194888 539929508 464086440 649927181 134601479 517836313 380954479 605977096 329519482 204905993 852856343 330462008 198008559 393858782 2066358 206350726 623853968 216009588 783214210 587295854 763301386 648216411 99169586 403809886 640785489 400743260 596454565 353135131 987493290 70796016 38347076 412337389 487030867 991520018 683279228 648121206 277735273 617204355 961052377 889628854 827811574 614281954 828064287 235691467 892732624 792954276 646118307 819705257 969700204 63953359 637521477 669893320 568528570 253495954 426569817 88204 649375883 825371028 894203209 648389267 532517719 524962773 817141908 764905139 178420620 492965963 119395229 404390802 728469696 733284747 491299489 292440140 362934322 299210017 172508500 874583678 411015397 100679975 887113459 538137284 502190004 223135401 706460553 655514682 54376590 519002236 839347887 782646178 686688971 931503484 322368647 410778843 203710733 488186945 96675886 299642280 122814757 939830061 50773513 613113402 197694537 902834361 896555801 906617592 826575735 816743062 451394607 655405829 615042949 158488337 375265042 854054407 464672890 988026696 234453778 132708971 939942785 285869179 105725807 658036356 788136563 650639359 847297715 3349561 994243905 592634512 975136905 478553692 509533034 524829105 388743255 109083611 529639452 593960152 790444329 847989656 40726429 775013456 411865817 495141472 983052652 107998365 612050988 860117174 788833604 291545678 997470139 164377784 237967789 923641689 509588657 341942006 873434727 762774913 737043824 818727701 726718291 103303763 925205618 856826300 82925927 663017908 176802429 349958312 264830730 325635293 129193026 132137087 367598611 474191497 893578457 845900544 294827630 611573348 91904488 984227302 962713745 231813768 942872905 207120482 298990779 534257893 507226131 390082964 323640256 996465567 947809323 166581314 526441921 617066558 690888276 577684217 283782019 861288463 756717521 137869353 534433021 703004626 788972000 704917384 514842063 630676051 755354270 91630297 718314297 263171531 701978456 542193437 220222101 634722836 3995137 555470358 974978039 643903263 758658824 213618496 805880453 821970046 201289553 58483619 366407900 462421469 981271030 87030828 962069575 216021027 18418112 669279088 685236933 253955574 464623771 76240525 659141805 853218186 290473422 665571831 353644205 6391773 570169631 400031515 139454026 732933867 702626724 691145713 443017934 736924821 617723586 394096753 830710776 544904072 699113912 361040465 425663258 526702885 999695468 980398085 255593984 851669839 411220042 337086093 683863478 800513813 567576631 329539017 352158904 716125988 776541137 358291641 833663627 121448857 405004926 107932905 549995795 433022441 786188182 485195850 184841774 268908630 669367215 321827168 92145622 13080922 255198553 962428501 4238734 500743764 227468924 300060838 916006071 811510397 704828138 59879409 407517164 743836013 22587768 828371558 3866978 634360485 833558539 810845984 294578755 966188018 774349472 570867612 179839770 498506276 622222480 649849305 460297222 506883750 262572516 476908684 670594660 831532879 206968331 101507410 483629384 256105716 376869587 809060847 65220129 123786588 49527109 871248253 619797312 346940303 370107313 326312763 39258219 216690442 339872074 5180647 199420847 422428262 770936746 321166079 578853533 786902657 924587729 794522228 807922856 17965906 130358761 263242521 73488019 878523775 741684332 966880359 257044434 935249482 705840690 228130933 112192312 570394889 441785214 713757105 750318885 375419932 571668388 664142611 861701373 973319854 420792519 452593388 515254550 892490467 901782587 985161492 74903011 884641055 34104697 813486824 930329177 812691840 286722518 528810060 354498986 557744850 723437223 136957643 613652539 59809649 840423441 291699064 35346919 325589023 812714009 673930297 125919440 124359982 704214186 22026633 466506609 49877328 495198371 633604446 987569565 521439657 277739908 129871963 175279167 429471154 414100813 727619629 913924653 422364277 435921673 418312155 780691448 105814094 373071660 813790202 79566866 313704711 490553360 9329931 909206966 809603932 690695295 74616776 134915403 444638917 33185089 225515919 614627350 157650726 723115193 958954024 115587767 73906095 542950602 184145255 65225892 673169271 789069881 835156525 443056069 758393884 775344486 741875588 52297615 153103468 163070605 186871517 108177664 994860555 19717863 469647723 895143422 687798073 867491563 514890833 187918587 941008825 501743073 71029251 692917250 948787985 156297788 237394025 867829286 856842199 605879628 432995048 552677233 116053056 558318168 326303251 229442142 572476448 287822038 409830250 322204133 968278710 837858604 521271078 256981436 538444754 813673837 434371391 907013620 661608450 622132343 893957155 85506799 527565155 644848249 617511122 808575204 758049034 114687125 308035527 73910641 927311444 657226162 43867346 837975639 413553147 340585266 277419919 955279844 965483033 453445804 920581833 905265648 454755666 324009112 495975250 853895010 324592537 670354254 449739341 877743284 115767287 4351691 591586878 190938074 413662093 55086071 943892310 576617523 119160461 109492468 309666737 154745199 777273386 131680517 500682984 719856285 374052631 128565423 441019819 535326490 953466652 26074966 612447197 959026134 203522061 33558445 18731124 458501024 898425229 153579781 709108701 802200490 595701902 618441834 226645008 991527859 13072554 36967373 15522934 469295105 922981734 792310157 222574694 48262620 81641775 893784918 327524542 243896351 291225663 95699307 234241881 229829171 171662751 971559965 554496745 104076963 652510993 99206746 823443373 42742234 912961711 557461166 443524565 118987679 395835273 680760538 846922081 916805879 996561977 492727398 980888278 549604312 764716746 780603934 217635864 686263380 956604903 600470002 724069646 713364089 650340099 440225154 934472441 844259572 791503922 965402521 31519100 553473810 721455754 185348266 883234840 11702568 58745430 532730537 186818318 758562047 146829090 3528313 603313297 34124870 587760030 741632073 476996706 542397060 812268370 797694394 764758057 832891356 704465048 555046006 388379780 545542678 483691000 441948208 327506044 342277322 774885604 534532191 538852693 298557307 544153487 888854328 106710869 174481686 393719426 264311997 884645424 636099322 246352680 792737640 266339969 959774207 262153930 509508774 755837790 44368412 902300168 44180459 42233871 417542077 754267495 105776987 40851106 719532214 577526428 600621880 207529677 744852624 668740785 727140540 4843888 144294567 118872907 856925644 568478900 327352311 190203283 769806117 919418053 534378687 753307952 425012017 751142564 419076259 461306017 239998946 894532404 321525404 67157089 140466187 70765538 190245813 532116196 632072439 125599527 732716510 436985107 444356934 694149284 97799030 797933431 133255544 133859865 258595944 571037071 235335326 754770395 424713076 613880775 463504205 645916633 720124470 210240136 529600741 527078632 367870796 196795474 782590206 516903389 221841266 384167563 506075995 611245434 403895528 271222331 565980625 69748162 933505869 877296259 775411532 909350609 149993470 190376797 145185911 53421061 255302292 456478302 65919993 719006709 566781450 948641971 996264217 863455877 864270443 698280702 431276246 605009667 244323742 656581577 988756887 641856661 385521700 354675137 994523350 375976222 335399333 252600204 865157639 22740063 912129553 993230448 656979137 163311238 191412262 915150862 263336756 383111883 38504119 766694830 220749927 312615655 516863595 84647936 492788017 763749129 355754892 135869316 743319092 735095834 335804700 223018254 361332816 780109821 966028431 507200050 793922730 615728976 876084536 556934273 138428365 404341553 854544514 873465776 526497472 880750590 564462536 393851860 388395735 310641819 664882583 69345894 169707473 313553923 96481472 788422198 252553121 111381621 726573615 625167388 165087276 68575013 705634133 558136651 279430482 672413849 918069356 929315169 404975090 51565374 241182481 554895619 782905727 297415402 374078733 402052421 280093956 614139224 179109027 106909902 953472180 4817824 768136693 127755901 497868797 326751303 170306774 54592036 268277607 209835713 675887186 159545464 348733743 618355269 669151075 969894981 112646378 112119336 448469867 632665012 409632180 401131715 989756860 33929808 693058746 95986123 697803341 528406834 907702470 397057155 574337249 107948089 79873328 453146491 391037557 174293311 14310021 453771269 296473638 591272916 661494153 450348444 859117977 936335441 226229796 581917929 357440966 673258028 284576462 235385677 81559356 854694834 911602323 444366391 291090202 670150311 690159826 448132673 167407179 195713286 273542050 88616415 574094446 162739332 306073819 16491709 838931379 334987448 270503990 677317831 668610959 460671983 795442741 373314079 64824477 99204461 408591578 272513022 52039758 92019251 38502600 430039655 468188131 80904164 68586614 315363200 646536139 776756075 854547502 280496495 603469545 423672115 589983826 469226471 712764835 310914218 975907876 611449122 85045959 414963381 383141706 157916282 788500377 830850728 954687764 774104285 977937649 503881530 765965167 10123980 30066776 837890905 653005947 464630065 119944877 651117722 413308413 222030602 659443078 759629532 80566204 508015109 227778791 583297619 643147620 485098692 539214238 86255925 951655814 719763290 964105996 624417603 480723094 822394085 12210846 62794135 252301896 348532759 252038282 836590449 176567370 583130657 380551167 806239788 768788447 169980218 662552568 186568722 671362049 773974832 474492764 828868631 6604805 832044050 72222090 72903840 614092034 459132788 62078014 577283534 272878578 978294069 799082804 667197271 580537035 426559156 72684144 705375603 96368124 928019278 57491291 853869782 837376442 690065722 58970213 317873525 181051510 839291838 380914572 443152201 557427639 337931309 866934944 726304537 366176028 823678445 603954267 178762187 151288616 199174106 492683448 553399527 937285403 439396511 890011203 352181137 5002486 197408709 214378541 584022710 516622390 862581901 669101052 935661202 137722320 78374700 468507735 980739702 995664274 586544480 390035593 221423833 733574239 81172849 162007996 269177931 902921633 827196966 520002025 431627896 217215354 910879567 719540830 32926068 277023240 615664086 379498793 621059815 802748662 749824266 537818322 754961068 362511978 19588817 941248786 554786030 687913218 767621867 968930902 217189212 713033528 964039180 496583570 708214397 742228312 691951165 460763330 960455243 231342326 193872156 329959634 281528686 96669436 798923925 865853135 587428929 784801053 562606081 643123270 910211936 478046167 134720724 569197962 144990965 233962985 690081602 280126649 449119880 52525720 218739169 247989736 39851690 903567331 37103667 531501649 364118558 924850608 136434096 387725502 457984995 246698445 858690997 604228910 663462694 176634716 668752062 550486656 285974367 633809113 249836032 559619901 19957334 621982828 408419739 140564308 118146221 516689995 914005869 660955662 828499061 308916807 213819622 693083253 592002118 118530642 361001236 264423552 455920545 886474333 305252816 160295371 135066222 227720826 350965636 952806127 856576800 350549785 666068761 722228607 974881647 503860267 564304444 676848335 4584728 669639598 299456497 650116352 41202465 678479505 739376531 390108019 171344826 657857226 376529834 818180370 648787311 538239441 877897521 771282431 467676913 988590537 263595294 842613904 310082144 839705185 343578023 158378744 563790603 661249357 678440618 71858431 267535489 855793175 5936715 895438890 941483221 949183802 700753195 45822653 989090311 42469497 830532731 719270358 828953274 327938015 67575172 681409021 281163852 759871263 118205156 510353278 181337886 886520615 706033421 44880209 349448245 876868701 189481650 505923163 912577323 563862338 825688760 170560232 715270934 84205035 559332596 102084993 578063227 858691343 46187676 626840439 499778499 884049385 896673360 280571557 288031365 374637556 892910193 566418159 476785915 770490380 768263770 531934567 698538330 497415813 785865274 361496146 987449420 19431821 332054093 531810661 665683333 356914557 976186673 164045801 141891549 94439358 813663742 333485071 376837042 847719352 197680174 121876904 513440796 291836004 60400413 649247414 104843898 22059496 132963462 709724133 138880456 10367707 695037993 230133988 26405535 514047362 95104606 936362878 444989290 47435401 860718073 811498066 380479265 301179507 550007839 889716074 436383064 869048965 640507124 570671292 144777448 952003837 838880430 691906021 839577034 566457823 967963479 112858422 159853850 126181371 917480673 301710521 734341577 334370760 976440924 335253699 390461331 652715602 393597261 794689469 748261796 581542600 291851002 185320909 455647038 322777452 399147963 919678994 723572106 945805299 585266979 377855704 516915382 654645744 3089030 7278875 325981169 945261299 774926229 521070626 406251753 802443198 392757220 453723919 770852801 98090927 427678112 869934701 944196692 476333121 661018158 804594102 181927886 781565363 719230955 181853599 204286403 853882156 648407605 301169119 111127603 186298198 191531043 270364143 905515568 159911543 28880521 958198574 264884743 504012123 672839697 32276408 506564049 582689419 304432056 261029021 144379724 160706191 860183970 373880750 131273060 748168334 628911624 269371913 669538637 180967372 685007237 595146828 205842439 551005046 630337799 488538734 386659388 728328774 346196331 386019971 292394723 875130730 371829656 435111844 231829078 626828119 917428641 744733341 991218962 16797 574803327 553037492 264240410 301135486 181953577 254116643 549780563 591834662 778740665 116671984 30513533 174679044 493176873 586936432 229788313 277424887 170998609 588281652 385417943 647448818 986340973 513763017 704777371 371752442 310507266 657658615 744599898 91975970 682038396 298787750 132743870 493042401 618081955 629544575 276614292 179640120 205011938 758937437 567704362 78351309 897875949 316564572 997056362 418584469 605518316 51068537 373104500 343815113 173314520 788842859 990368327 281326454 471447883 379468021 962443293 851019619 985971462 209597449 794820569 371069314 649318787 577061895 800299504 337816043 339146306 353439768 925441598 452125792 747479102 469124717 241032012 825313229 720083555 725909052 941714011 488088640 380142240 785831619 339366587 486441548 270021042 876244849 589960983 779071557 29952038 720299293 512237946 382586186 195610384 178816522 509689102 487015945 855337384 871456926 539843111 124858842 688620753 125834638 892763294 446846362 965241585 360646972 830902068 378593816 891359065 209653152 460974253 255573767 545659482 63898316 460163797 380003107 923349893 302609738 508411687 602737450 44070249 346473925 207853928 334643029 95784736 713423440 465624109 680766991 764224485 768175614 538204308 981852331 691402310 382070120 239236065 930033840 854794792 929578493 546255576 191177737 297975631 832040626 199528341 358591682 852961445 766448849 233327605 827961923 797011719 893697726 642410451 898507763 395556459 885301359 137442822 701050874 755458370 924030363 268803313 959061576 238508867 2228698 115866760 738819409 131465434 635699590 421599101 888949679 638067712 141190546 491290224 581224394 189112199 278303766 202619771 223806276 422238160 856366113 427954866 210723683 153699447 261531564 533911306 343390712 85524274 182568531 531832056 867829157 93168488 527170793 497645236 436617498 819937150 159448838 179124587 979820444 308370513 236920474 72217595 112405413 21158376 767997123 520162873 628447400 711325924 454625697 65325717 596186023 576767324 768051217 832407399 736325492 631619715 96054482 422922526 543065950 299410522 824871027 227751739 674632076 783415752 573860191 8329458 328500736 540159151 136167431 696177086 808580353 179394753 494423949 331070064 818619815 980975948 476798645 769027428 395499475 531015486 314275306 953806106 87520364 909111203 778540825 325330940 341321053 602347251 630418616 788908743 133129584 757796251 590268237 406997384 730249762 925978715 200729766 62442637 177168392 712861967 575760441 394222117 334624589 675227011 630493451 315355529 756461747 102611117 817880605 319268482 586105475 278089892 844943825 280441751 330691053 92383639 4745847 641670333 93592372 63826927 213564697 164175330 376759752 736524854 796133348 602002713 50418058 409876984 842836830 839529212 299461758 393424120 431685841 322581255 283696445 672405533 734409021 76598180 861292277 945230553 240210222 207545922 382384779 271286960 345077019 121080854 947681718 609084114 676333738 902738330 170454296 817160499 250094423 541052299 453873896 889935419 812023669 538936257 4405383 56950253 57734146 588193960 4358517 4934701 158617077 238129328 216619830 417295426 412544169 883539875 22127481 702891417 142891797 360684994 415247673 211319544 907432992 673042111 497920881 827823444 148296543 144017447 258023323 689510724 954720167 341217851 780537836 288956195 808678455 120954793 601453763 449256976 831207280 371417667 407849780 612831510 584415272 735216857 951249461 652437870 963680396 956789118 348587528 176810456 474429367 560962328 547785977 631658755 999288780 840869463 362757361 908919143 70840224 948823354 953154489 351174206 890180750 78742139 503255966 35413628 466410055 884315976 411058151 292915972 665437889 193161243 15053954 386370447 483522558 973886109 643285264 343866261 804265763 352953110 379896315 659868486 552484799 530838559 419395045 600926578 917342849 346830273 517780681 892416404 774328770 99995445 889166903 10854918 486402123 836690905 346331022 159453822 553406080 579501298 826026512 964073742 568454544 275431365 907433268 608622353 639020866 883522480 724020955 434087284 468639193 767399375 538451104 462060181 649286042 237988341 601455355 60990782 610281084 428281880 731446360 227064599 114573893 122993860 69413813 386175561 515335803 844883630 165966394 746061297 731737385 606187408 856116561 5555335 103294874 205285952 245037663 56390324 191638951 977809741 121121188 676945978 173571567 437376442 595548349 399973999 945396753 515712402 293840842 859497972 196846828 697403482 613460011 151895662 872697062 55751846 450312827 326718756 619764594 139430530 225262098 717293164 542569879 681363601 742126956 103709000 546272796 837309478 535265577 308001532 92363721 668213743 621019831 990446955 14707211 784244201 862957961 808797357 775766059 123774570 75818948 580128749 355995174 34813100 294094430 423612825 97599202 442623187 45996083 254512378 747917485 650326619 428459626 775182584 552196887 243915346 351616391 767159106 411465484 173526231 576992069 427048596 230004364 837998716 183193757 888079873 161834740 738265858 626338987 113762473 633034713 631922225 436817738 138226179 609372070 198689884 808258130 135589520 165951009 75139588 828066334 991185907 95269514 482281247 435187482 180569922 770211688 97057314 433972313 751429419 438971585 928683840 606460421 817971681 857827830 876851134 176113908 633760611 399071138 439923537 613318379 433435407 692177434 603282785 612611402 872953342 982103315 533945892 295321535 783105925 902377376 359608915 439212847 335089293 594393749 901375459 296587686 652568861 626677588 943319993 884388739 808138416 275355067 393084831 709579825 33907657 382755320 255077504 747382204 813820469 178638087 369510989 765592600 300842891 103727861 86167652 127241770 967822634 434894060 162514639 405156511 853240132 955506012 106060266 643626406 726021131 743014836 874333693 357070278 691154348 828611001 890845014 247012619 692727772 439953495 462629043 323187630 312620404 293888304 469178152 351136346 846065827 111690779 741945986 766004032 409363594 889670397 514420938 630629525 863264391 154763336 666159953 628541308 107632004 844117355 809547931 944734386 735852608 25483572 512753644 620654280 43467675 958156462 99608850 832654153 211108332 280942459 329948750 713960699 796771945 393390413 51214695 410235587 278647103 724037969 4387479 573131758 298043900 934640492 696935157 121286069 436378695 315414982 90296175 33032153 86776390 613047532 130296287 201700020 362357459 537636706 576027780 17859926 453222520 915625217 30952694 141722250 941423805 640399593 701841021 231361777 979218306 709833446 410721961 768164947 843866065 793868571 723235938 122165500 598162337 308892922 141542245 943908085 451411509 721699194 225469904 864627518 681940766 528568210 563662604 322151111 195234605 866559548 156946544 755076466 256207729 399031583 669281729 762983243 988462863 71545317 635866068 394650132 206716892 923713507 608300359 497986689 622077203 737921805 720583190 960869513 12288557 693238409 135460097 300845004 912062027 159064347 619959615 204505373 37390449 539350260 979112833 151765299 230089460 368678047 690955345 945099331 311578395 891910083 340129362 231339549 546266426 617959996 197742722 8192955 38815273 429106304 786928376 472912402 108567569 890809987 933150138 171959377 309814381 925663066 120888830 946880702 99966132 475101134 898794188 943817657 459900488 163635886 721256495 80310113 859940965 881546037 837465890 445860380 894056351 145364559 71138415 669337225 698579252 10419407 998224715 335382676 408654167 354311646 185529672 580071151 390273841 792059618 814930289 23632298 190568189 81971366 728434144 369538818 984273989 503098614 103566454 776607723 226030029 212223678 499570470 39954642 65592006 700421912 841857481 2931289 677236739 971893537 91161598 988428696 847229912 837011653 24669181 838222885 638771773 102446885 343884611 212996527 952216445 402778574 150387536 763817536 386746352 146874913 518404578 658142458 569082854 397561091 762367706 385678584 72788365 480398090 914973539 696137167 510225575 498494626 247267476 137308597 349581212 346711145 813339893 290999284 75402587 998837187 271792102 284441101 983171860 994406036 765042240 396625548 24200671 777935996 827104493 208253456 946883060 841642047 578079136 109168919 919603519 115843431 558075377 424265839 333297809 354276499 226988453 254960876 381809772 217398038 864095175 374213069 613170997 951289564 836339743 773863145 364810913 853570818 305861391 127087868 223086041 777424042 601253487 684730787 136787676 647793368 720266061 431280184 363358766 79617975 273296054 215358081 141407525 243965666 84432356 279686380 282669521 942419240 805656468 167665924 937928446 118918797 950350626 725746008 346539738 646135811 364579567 867413340 984406156 265054832 571132604 839626903 44149379 947569936 88561022 588020436 430205391 151563290 605955424 800852523 932279219 343378396 784134400 600147622 987852078 740387401 306559187 853972095 602220421 473272624 365959973 641150324 267928076 137067117 139120780 235455754 450625889 469416645 532741876 585239237 460175684 419001952 813130433 261348870 82168396 764043057 662676061 443599548 84959377 511896892 808347606 725194829 940795167 642096184 270913036 897603380 438677160 352488153 25033610 583852988 620076859 202204808 675719612 909106103 992215847 982097797 198909088 881322649 692662002 257743994 585864222 804272166 360961690 875034949 810341829 604828466 551930417 239852195 134800253 692272562 77244325 812527298 904666376 828444608 628456439 916426750 532503970 330307366 495670498 285607739 840774018 466377950 133792189 262091782 553954815 642864971 324536848 858733565 10023763 96687510 299737847 59839664 141274366 914615535 268257463 789470961 290034713 516396187 817408697 496339658 752736290 326159086 658584071 186191163 229772431 953543608 424560403 165539079 659202812 238963390 16092782 436627744 766396002 334333020 610945460 155538961 231768724 222884649 494089845 930642193 150956631 20533383 419632997 808523338 882252431 721614305 374225770 696764395 688454166 829924393 89415599 800400293 280766172 840887302 742093005 757766163 791716055 766588177 366454376 788564004 816081089 218800842 326185297 887899774 801229849 955367038 759049866 598921228 329396868 630228519 192582090 563302578 659722578 929339062 518223488 658267240 193873001 957239293 459032913 467738212 993051030 246675995 687579645 980423301 826446951 969880634 607620023 302373139 310266989 134496092 148646776 939342340 945180009 781711729 460761770 865727387 194865856 67413378 821691466 312830756 276971303 143125659 118234489 776100682 679430290 135238378 794755503 987245071 455118108 830731201 949713731 911436043 244568060 650829219 766666082 622402589 656288554 859149021 634591263 568364999 908231482 606671012 978215521 385912219 70227412 15173640 771168453 609798553 767421389 69318680 717939211 592307186 115582364 838957174 985294260 826797733 273663174 163017814 25137512 472123626 888750875 952869726 894451934 788269638 262734636 264792604 667958036 146886816 904920236 132101759 596634955 43676481 505110178 48164588 109558931 602321668 375954428 412732553 550476130 678379479 179566627 256690865 944701891 178567241 618813205 438432309 765997846 560523878 632819320 53067829 976230903 920830727 141483698 604424792 953890765 115442968 581354134 841467072 283346861 211048970 198942287 552989011 489856268 161024071 413715167 662436353 335052389 558954777 457773052 305372785 842068770 273244404 357036040 564909585 800778278 355266158 436717987 909032028 329381851 426223758 365215466 464983944 378911388 160544287 812258820 511407315 398423090 854409808 932676272 42884531 275290043 790652811 13228426 661557495 999119536 744957630 244004141 783634780 904083321 609700162 590749310 393306230 915058927 842145128 352552202 941961368 779906364 268497426 595734862 534912376 693369487 98848822 270175142 307243429 584147116 594768389 760455565 808965694 707283504 213315680 619539727 768210601 929253590 395438363 232134313 687563344 399739984 525442061 687257819 928182680 851172605 770226820 91793406 870737802 193492685 6180964 338119744 387570237 714743283 676160844 535863612 849874217 751980061 183425674 920367751 395011064 743175447 372915444 347574205 182339857 297808350 384045457 406752021 985822275 538447104 737717282 155302255 409271171 181661888 65052048 376206063 941689685 261143685 766903637 436386344 436622024 967294124 873367661 561564224 199693478 685981823 173715324 240962383 248273229 461136475 270596086 877729580 821962448 583557357 552239767 155505136 228018965 51609967 181899396 166863973 387958332 955450227 793163331 556215604 892330798 460115468 317952053 7851346 73967078 615931379 904242934 601520256 123319813 388838835 142157038 783089770 736361557 455773734 623818699 687564135 201613440 506198864 976784723 468781270 107275904 515190573 472075550 661490539 978174970 280206688 175772083 563368144 812958105 443392157 606582880 132451170 733449215 771525482 48239915 88357421 752981348 373612817 255929898 466040673 389736446 730842184 296800420 173133239 634191945 582844912 112173083 846247968 948522204 556435076 285769233 741588928 922581995 238891138 684010333 206567420 527533208 865264529 312373200 204959646 391070956 492195367 37389730 64296473 702475116 808500888 46426302 609982436 145018816 153234403 959351155 912594876 312429570 501867617 890314030 273163611 661230713 814425944 113819728 668264750 803830995 128559448 877146490 442571084 9260859 261558472 343212316 166772690 670860216 956801667 986555542 978946138 107448810 941179379 257683993 347921302 939565009 946940829 859479825 528743464 931287848 518566598 609570090 22905164 831472821 820691949 61329401 536464612 906274030 278749610 658681363 583212660 261980306 563604916 818540708 741188072 248336903 572305942 823112557 248020418 476563576 589231986 618207603 725063624 458385265 536891099 586564787 20451043 622171305 809867161 168746510 488791654 980624317 481045075 820216654 442022937 889153818 748240538 444980882 958438335 17396292 950565854 495595633 985920021 967175956 779363242 636413473 627087483 336691186 866814760 798527239 182136688 238349456 252352316 26071908 51814929 826802899 415532461 475013370 658790532 9452060 812012335 463024844 722757286 715119582 962625964 425219636 849879215 984300416 120683817 121015495 404703967 325437635 114198895 407943572 987655259 795292364 612134238 964160727 30480041 613702839 273178773 491953702 966274672 658716782 219905295 489919156 800110435 669066562 285171186 854271519 404318682 857178516 273338575 63826867 684820636 998658332 391901339 271129683 665878284 910780189 637792920 639711594 945796497 807867880 333928983 743140209 463590871 735179586 671718657 741565231 318950637 639587110 945122666 669209643 585341023 265922194 692214185 753605699 651867368 956946216 68617628 570909458 547348403 894495655 784695326 142788706 988715852 312794555 447980832 845872815 990127694 511999936 739920818 541291295 364127288 96482863 550149007 749333473 310759282 302840421 331109984 468165553 893633962 404080572 542931224 32736661 538285877 422541549 809663240 883927932 773595750 54900766 836448748 625189911 306195816 412943192 585648784 147524681 522714214 441460082 118851582 540717953 391549945 622728323 206075969 767396318 819879218 340370508 43806746 783350177 836209315 271148334 333315311 944816302 979048740 39982734 392990670 858018371 102159248 341494791 316371514 545186258 219984763 292776971 745334685 482496806 327202172 328687020 213992920 61853666 782452352 350936351 177462685 263754995 360964548 203066621 81839045 67422394 916725763 694437746 398098999 153764479 469474393 554707032 778084553 924297443 649268455 483055411 104408508 157716428 105429089 429804639 749653455 789498467 915292861 995251036 902244945 205263085 496772611 671518251 627692791 229885923 909549225 445717142 472515874 138788385 187686985 806713839 327767844 114925176 575615664 212381147 76552695 513660671 893645586 276336923 641940894 195878273 933503427 667358713 600308105 707071175 476783372 241261473 394338784 798019670 572264654 520336547 412194378 768876283 447758188 632039692 373865393 483811798 255612653 433707090 332619528 491420902 903463874 748301937 992596839 645497489 932065966 597855253 480681626 836264641 59278378 222700800 403963913 738687343 931847076 504716636 73930040 787502912 647395294 132196883 872732739 387105075 410221541 130723519 176515456 951491213 306700270 289345907 945346316 35347315 92436885 873770225 376768709 105781926 235394435 966831457 481555662 40170954 503012390 248896787 707955067 331316272 142743274 106945703 989664765 152146892 313389508 811591702 717432583 774405686 616295210 847182798 562393355 242006126 335874942 343673075 288064532 777547979 998274606 950815940 929294993 154056716 737474874 601814427 211273427 223120584 757895617 224858958 782840752 382682408 876920520 235633967 108311243 186671154 483700781 955715631 987510934 870749261 968510530 856842336 728622970 205488969 200778083 957305948 629500579 597876334 731640879 349027282 363474462 936683271 288719597 903052474 872466218 57900263 465971205 239684838 668654919 574719477 514632800 301220298 284017088 858919755 691373369 442707649 435010613 723978601 117023448 277648100 156732559 661696523 10140092 59642364 170595982 752788622 233842370 313048822 758756019 264250512 424408572 146000581 813134726 976863265 746897207 431898166 184142286 212878984 137016554 680415276 397906378 813948078 643516935 496769756 980062690 904856595 76702394 600928670 276649208 754855137 484344437 357623079 782503773 29289313 988073225 919228715 683344208 998029058 787327896 415999705 359570777 861904080 803460831 410271835 343428308 728837758 183627939 675213860 816563804 739360084 816602590 487127385 856086583 228936307 828259144 968148033 478259216 476834462 388510765 356829244 882693420 199316307 823912135 511841878 350243807 292298442 180503797 431204398 296781119 507606124 395104870 314052850 683528910 597404808 304832143 616517365 400778921 775893195 21085313 499699046 370163277 965921326 416857703 78034958 544528493 321199628 129904688 575004424 846508491 639861181 21342660 462743356 728132005 549309114 787953367 711752254 429688776 824418348 478277839 459670558 899116149 556181389 336777893 176144097 186978700 38050324 501451836 777256736 602267569 42640957 715774553 642417106 320799060 881440702 364043888 643006974 573344123 233041412 454184131 237298891 136142795 869807870 563804601 997957215 891404987 662880213 789427696 145609816 392308951 833175778 358724598 160697738 418887263 931687651 198759236 527530009 761589679 79725342 415187042 788431200 48493679 117288870 509364663 657898675 652739870 118688728 941045782 406583512 649674607 791109609 847467618 81465261 617800909 411637310 191635342 425202176 555935489 87713165 25308422 388878168 422263689 608267887 490257532 369518111 531844033 121233490 861752246 2439453 61352937 783548150 200591266 546793206 910316005 498881698 596513920 191857400 451356682 7917664 171224255 360600580 224184228 87747032 474422546 765900200 361172176 134779237 773263821 839831970 457968666 673114540 942979960 40163198 38705956 658739013 674264636 580871186 178640441 667708866 180760969 681331781 133650635 92753104 762427048 908626564 33809465 632822218 316885166 544324554 560661067 463119318 803234906 525613980 565467136 371504872 776424794 398959283 558474689 296372635 225341679 22514787 222823037 944488253 683327006 830896963 261242868 409419771 28804399 74258736 659136300 495941824 680232421 120426418 985273887 78319498 123897702 538064543 198441837 168733708 561154000 366859640 741839134 288434228 683988742 912464330 326705178 767281964 178935033 188622676 348691398 997487998 984335112 651363124 595721003 230006440 839495038 996776305 77454309 605034785 150301414 910047179 957140349 366308567 764551410 785884164 669067251 474913154 241034298 88439231 959142521 456561144 865001778 190031104 59837195 80186391 631324391 884958608 728121154 552180672 883907038 563593339 463979457 649330559 418272456 573950257 837470089 426109242 358623520 226004327 783326092 639770933 427440361 805332997 229463416 716254508 373015081 244464964 467939103 750986943 839183156 992668192 810848672 362225445 642211372 839172351 127257888 450293880 881760995 116789689 949143926 424634084 820297974 923720917 745960600 301905373 86355084 804950242 923446634 400740665 690354054 37642736 161035769 344974002 684483758 726154210 348394166 277865440 974762811 150587024 583584467 652060064 446289637 451398844 791048331 210318335 30193159 842483023 72071250 919138617 586195757 66770011 554277039 168050200 189624549 886034744 768933575 958625124 87450477 550816386 614223483 470803346 617112565 854179567 543659424 971817379 471742789 682914460 857913099 355627063 898482575 407514918 676171027 423337447 361704645 201004402 580235273 620574518 578207988 328000119 624452108 850247522 422797054 208330916 720740634 109510681 562362397 214466396 868349239 892380994 17729444 328416831 762435364 741740958 493790240 151936459 528064122 624108278 744545819 205059086 846275945 912444371 939699379 761981051 567509838 961378640 493606108 928440271 747089305 403249644 673189045 656763816 752663011 299255991 268083216 742242238 610780646 600010896 447400652 589237956 760198483 119883184 665805585 329145053 158936498 493711265 712307987 584475812 572978630 522395472 190089481 924562567 251303534 721392101 223662350 1632599 663209820 286847377 524505460 755639296 815452764 914610610 646869403 899211838 182978468 960165848 482502764 155272239 617965050 49962067 539822069 932343800 622241990 590633260 917674801 593848226 349609703 945490095 589877763 738716343 467336224 516497088 968531550 225785009 7575563 646273226 92848135 746217719 222940466 903321411 180689811 542700182 833099985 509556653 956354774 330532959 743795893 337717155 539447884 392793606 450435995 888927361 420553988 482305342 880140412 812757974 17275205 994619165 284671648 414536722 811684630 584579543 712861397 20187654 307636595 981414314 868242569 178055302 997111647 315647189 387295933 600268150 990225517 106832195 705400119 103247432 747468601 816730738 101126303 930215469 773047789 951911007 379742450 868879081 823727407 987162559 159318483 634281312 77244766 167575592 763004316 59365757 138800735 370475330 756685869 49791447 309991824 384056458 444172977 524820336 421110837 48001275 362527877 645345298 444949889 791399965 129069017 781548050 434109035 260024251 959863231 790233875 224928541 510074489 976624873 130642710 700252265 399428538 968862001 733329384 779313091 606270083 199667709 161940762 198854173 340127878 387149918 687192965 481276099 2636630 488599205 591474850 380457426 676140932 160177733 535898389 703207620 686988658 713922932 777815285 141722203 226605546 154881713 948342435 650802652 729586616 451539598 847223831 326064093 690107824 99643974 424349540 766493863 80426738 615588186 392565283 421353430 519328962 831488215 40866551 703529418 103947099 86571392 831984770 521053892 855190338 72031845 475727180 194108556 92367909 948090430 903132391 383749372 856817022 606075384 663770677 652897304 673355729 265842147 603890381 706010985 383467934 310883781 312742276 167229236 281469295 607594639 259868620 273854814 727198639 107285139 44051984 648790925 51852427 229700479 934048820 126483458 698515973 861030551 217174968 462499574 481460310 377367867 469245874 231231639 696973245 70293101 922395905 813605640 867624223 958499089 619510166 425650326 956027937 137651334 391709824 760444431 399859240 670575292 309646055 30747651 552794330 454873040 218524352 96656547 592839786 824532728 700349429 104844829 962847694 573497406 127095459 845154583 608352034 236518014 880743798 465615154 348550693 844495846 850560409 187346203 971752657 833593846 645160089 154367386 515129180 104825037 862606155 623390523 780177768 798293667 50693534 932331038 33232704 958791545 120320725 823455497 412119578 164404453 740902133 160082685 216760744 17940151 140245079 918675821 884916535 566331384 591669313 394679217 18246251 611732450 452311690 934105173 771694635 527484414 607178185 730220400 844938131 333529884 496688630 38766874 871890444 117312859 723187417 159635236 812209388 738263858 425844378 120047309 753228222 240993444 786755342 476483174 952834079 204686413 220629100 74896824 387986492 326751444 330205839 684391590 804422643 869617526 549452180 394856167 800105288 301790294 971417898 252479225 74355230 609797574 426699345 380470213 592862040 551734709 172348970 926233653 175456549 530521396 549885543 611707998 824660555 792104597 182649821 113810359 838058444 714669454 236323121 839786920 85946802 921332610 390532105 224101595 406494415 402377569 778779047 865356113 54561118 385669371 984787550 969376018 769587707 668203191 729781592 506405265 373435977 805493487 900341185 908087020 324261076 303688258 505009166 762870076 436323127 841445140 629653965 41541198 572926198 927691821 417670731 316589806 623897625 649998448 55691611 331134708 865459691 597777950 201263007 456105385 6010870 261159513 547756502 789989759 338106515 68662715 242795349 69527091 808420934 975158604 618160749 670502143 622424814 735882211 997896405 438275335 655070248 888992856 187096084 786288283 170394269 882402773 13059808 19729132 485631688 886569811 725602043 718254759 855045451 469239920 161076794 730288983 664026490 216916190 679767370 960501225 261779432 423938900 52620847 131725318 308692136 224973366 769001070 609673743 809466700 349787804 708008186 673742189 514826593 795604484 995501202 209627560 746520083 521459730 838077069 150897090 618955569 876921808 482459360 884181974 458978574 399653288 602611517 199212143 210540862 317148362 708305528 225573231 921429439 878597885 314228300 2889062 388062456 905117945 47427201 101117117 815630028 810652917 56348322 646832977 371742316 779866747 104123163 964058551 268735287 144592334 519260381 476135675 370763350 555746039 355182365 309956337 10766889 662511698 331531906 357819175 594832068 991438550 890712003 761195236 254473234 770807878 92209233 406519301 303090547 5450790 443253076 593403898 844452141 529933732 151294316 429037709 78690937 353020863 999106683 883910229 990542410 239432492 223138004 170684103 158389732 377916395 955167620 887642395 881609506 658798592 453583525 102710902 848978932 538810131 27371531 579684443 447194583 197672740 16266362 26249102 994374478 967497590 890899165 143180064 179529063 247742339 379058563 482313411 360761408 488293804 568016944 582958151 261260774 89689182 699716596 128481302 242156379 924189870 142965839 982886684 878728174 714960715 348237608 377710753 588759967 614135847 330035152 185466534 84259468 977592116 64158059 808493702 83946766 183500263 620903759 312124860 766333943 998706648 910296005 906058048 421878670 309352070 289206833 638647051 290631491 194770992 561803689 850676116 173813993 842337248 3776418 981093930 319050467 247899022 178180222 208507344 324196981 262477337 925380533 427136402 108827344 491630133 963510854 393381338 561456095 623445970 948050263 305971871 862700729 207091643 19690297 43904899 866444188 485157355 495439873 726746757 131103669 358428604 333277810 538204017 850122223 385692030 574407225 466945248 618906598 48665296 564368739 115282636 628864906 97643930 691383227 837869658 487686511 765803092 405555014 749283632 809238145 864475759 633243028 937813899 198653125 441654476 672483284 755460859 446668300 624721530 643346923 237222633 819876879 398726659 687254270 438343049 287332272 333450245 689692839 874910320 362618450 980316196 999489163 6143745 162248251 919405159 978080380 131648274 161049831 298183546 424812949 70900535 386027081 278627988 621993178 106948256 943531224 549967865 327756298 875828500 924241136 278519709 310847820 229722357 430406808 220765769 925768128 365887317 947197820 627724583 670440653 309782943 870769884 264649945 90031788 353656895 622811636 691685669 39250981 897714009 647805878 204601167 793980790 624791265 707631042 490971861 957098564 949133866 412270737 629172026 601877783 619134158 181555262 660410413 471750943 721619849 241561436 725893827 373589080 265021680 332128116 785973264 881228319 330360221 493865359 706676597 362719119 131730346 266987331 407332879 898984449 859988754 59934348 420898978 255287846 708417743 813688779 265093326 327130159 318808815 556147457 194596435 56011967 851206554 225086769 119456709 736732245 792167999 952342852 664818146 213726124 149493564 640761139 596929544 522312186 850513753 676727531 558480682 650868197 888522996 121964233 282525366 202046892 979611872 157479826 479623996 458688653 524511095 847405555 538234313 383121143 888298725 966647297 480700062 871221267 893937175 109749545 76269185 155274266 826260836 439563536 804560302 565788591 452581036 428920726 197571914 390704931 536449239 631669106 371592879 404006177 732062941 587395131 667598297 864618354 606157706 448432797 618150493 994474268 779399067 110359519 298409147 191870920 429546721 349151987 171345605 811579156 628040934 939049395 823139318 945463143 381680325 749337803 662696870 80314307 129613483 672635050 241960155 160058003 963903784 168305267 375368972 141592898 925399095 453375703 263630804 574189993 948227449 772790350 126305210 806935230 601827014 624074243 598511585 156608345 129431378 910487778 458521168 204251303 687524577 304568665 18621459 41336030 171593268 52910072 86269182 351231908 504784706 866882975 916462857 836887657 963696672 202101850 799256158 850589627 889893990 388249774 497692553 95411587 291396884 470692306 361616934 839975830 380068157 658560032 209052904 790989834 927305411 787525745 437020555 705386943 401429460 542794224 545173968 503771430 335276338 546845995 863142004 586241031 539862944 336034286 907546151 753924128 134803677 941434863 631903979 984188422 369763961 531453582 243599138 624935500 130978449 89605482 916081309 118226848 360140568 121425029 409807023 239032425 252806810 865031317 589471188 306060145 943529589 145511538 144311762 528723585 752885476 649915938 528660852 895363722 268480387 71713358 962449767 438189165 5100117 234208183 137328831 34937209 418458958 475000225 172358164 815639191 332647123 641236652 965480976 263063921 57342647 76524038 519709621 487606625 55798441 229120630 15448188 614981023 823681517 925948208 772364072 735726522 135467480 75068095 744657233 851966516 755460991 711826812 302008280 518167622 274359810 681506341 636344316 699489478 312829991 344641182 744975087 16927944 968219884 943179227 290678566 400263994 685228962 627412830 462051828 784516181 728383159 770762775 50253874 195960421 690577271 656683785 559290856 784047684 189971800 220675706 585768362 765337241 996301929 703634894 42861319 644281549 871783827 241711483 759054854 551509784 720539441 846794835 351452053 996917344 997599055 742306373 366272180 284060436 530480642 798261072 839470854 823881585 678916508 178707449 837371277 466627930 753573776 552103852 241024226 991556981 59277546 319934866 587956051 179787697 305854284 534627891 568327606 480681240 268125866 990541420 452982118 681110973 931445125 844116623 836421700 928743153 819056023 511152955 773287786 652554063 878263329 723559718 561363561 671755891 875728685 519946810 986149415 331968513 127688799 738171517 142024161 332518566 911441540 94960623 61501078 142507332 144711314 868150387 515012244 582026754 976323582 745315725 307146302 566794567 682561541 606264817 162774889 224940703 108189352 891356076 571570804 85235090 449694388 727287922 565230093 878653519 1146460 288359868 11223052 839136101 908144186 699097839 405380506 26909925 154727418 603927892 842551361 483623494 412193408 511072176 38432198 241306776 472513428 116600038 404269713 448106613 291459073 581237790 765389066 498366412 226628718 2761028 953728191 831783990 852100575 816514720 693714297 941600876
> 2290133
"""
from sys import setrecursionlimit
setrecursionlimit(10**6)


def syöttö():
    etäisyys = int(input())
    kantamasyöte = input().split()
    kantamat = tuple(map(int, kantamasyöte))
    hintasyöte = input().split()
    hinnat = tuple(map(int, hintasyöte))

    # Lähetin + Mastot
    mastot = {0: {"kantama": kantamat[0], "hinta": 0}}
    for i in range(etäisyys-1):
        kantama, hinta = kantamat[i+1], hinnat[i]
        mastot[i+1] = {"kantama": kantama, "hinta": hinta}

    return mastot, etäisyys


def pienin_hinta(mastot, etäisyys):
    """
    :param mastot: dic
    :param etäisyys: int
    :return:
    """
    mastotuple = tuple(mastot)
    hinnatmuisti = {}

    def seuraavat_mastot(nyt_masto, mastot, etäisyys, hinnatmuisti):
        """
        todo: Laita nyt_masto:n hinta muistiin.
        todo: Laskee hinnat mukaan
        :param nyt_masto: n:nnes masto
        :param mastot: dic
        :param etäisyys: int
        :param hinnatmuisti: Annetun tolpan halvin hinta siitä eteenpäin.
        :return:
        """
        # Onko muistissa?
        if nyt_masto in hinnatmuisti:
            return hinnatmuisti[nyt_masto]

        # Nykyisen maston kantama
        kantama = mastot[nyt_masto]["kantama"]

        # Jos kantamaa riittää vastaanottimeen, palautetaan hinta
        if nyt_masto + kantama >= etäisyys:
            hinnatmuisti[nyt_masto] = mastot[nyt_masto]["hinta"]
            return mastot[nyt_masto]["hinta"]

        # Tarkista seuraavat mastot
        seuraavista_pienimmät_hinnat = []
        for seuraava_masto in mastotuple[nyt_masto + 1:nyt_masto + kantama + 1]:
            seuraavista_pienimmät_hinnat.append(
                seuraavat_mastot(seuraava_masto, mastot, etäisyys, hinnatmuisti)
            )

        # min-funktio ottaa kahden tai useamman parametrin
        if len(seuraavista_pienimmät_hinnat) > 1:
            seuraavista_pienin_hinta = min(seuraavista_pienimmät_hinnat)
        else:
            seuraavista_pienin_hinta = seuraavista_pienimmät_hinnat[0]

        # Siis nykyisen maston kohdalla hinta on
        nykyisen_maston_hinta = seuraavista_pienin_hinta + mastot[nyt_masto]["hinta"]
        hinnatmuisti[nyt_masto] = nykyisen_maston_hinta

        return nykyisen_maston_hinta

    mastojenhinnat = []
    for läheinen_masto in mastotuple[1:mastot[0]["kantama"] + 1]:
        mastojenhinnat.append(seuraavat_mastot(läheinen_masto, mastot, etäisyys, hinnatmuisti))

    return min(mastojenhinnat)


def main():
    mastot, etäisyys = syöttö()
    # Lähettimen kantama riittää
    if mastot[0]["kantama"] >= etäisyys:
        print(0)
    else:
        # On vain yksi masto välissä
        # if len(mastot) == 2:
        #     print(mastot[1]["hinta"])
        #     return

        hinta = pienin_hinta(mastot, etäisyys)
        print(hinta)


main()

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

Test 7

Group: 1, 2, 3

Verdict: ACCEPTED

Test 8

Group: 1, 2, 3

Verdict: ACCEPTED

Test 9

Group: 1, 2, 3

Verdict: ACCEPTED

Test 10

Group: 1, 2, 3

Verdict: ACCEPTED

Test 11

Group: 1, 2, 3

Verdict: ACCEPTED

Test 12

Group: 1, 2, 3

Verdict: ACCEPTED

Test 13

Group: 1, 2, 3

Verdict: ACCEPTED

Test 14

Group: 1, 2, 3

Verdict: ACCEPTED

Test 15

Group: 1, 2, 3

Verdict: ACCEPTED

Test 16

Group: 1, 2, 3

Verdict: ACCEPTED

Test 17

Group: 1, 2, 3

Verdict: ACCEPTED

Test 18

Group: 1, 2, 3

Verdict: ACCEPTED

Test 19

Group: 1, 2, 3

Verdict: ACCEPTED

Test 20

Group: 1, 2, 3

Verdict: ACCEPTED

Test 21

Group: 2, 3

Verdict: ACCEPTED

Test 22

Group: 2, 3

Verdict: ACCEPTED

Test 23

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 24

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 25

Group: 2, 3

Verdict: ACCEPTED

Test 26

Group: 2, 3

Verdict: ACCEPTED

Test 27

Group: 2, 3

Verdict: ACCEPTED

Test 28

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 29

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 30

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 31

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 32

Group: 2, 3

Verdict: ACCEPTED

Test 33

Group: 2, 3

Verdict: ACCEPTED

Test 34

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 35

Group: 3

Verdict: ACCEPTED

Test 36

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 37

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 38

Group: 3

Verdict: RUNTIME ERROR

Test 39

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 40

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 41

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 42

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 43

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 44

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 45

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 46

Group: 3

Verdict: TIME LIMIT EXCEEDED