using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace LeetCode.QuestionBank.Question3154
{
    public class Solution3154_dial : Interface3154
    {
        private readonly static Dictionary<int, int> dial = new Dictionary<int, int> { { 0, 2 }, { 1, 4 }, { 2, 4 }, { 3, 3 }, { 4, 2 }, { 5, 4 }, { 6, 6 }, { 7, 4 }, { 8, 1 }, { 11, 1 }, { 12, 5 }, { 13, 10 }, { 14, 10 }, { 15, 5 }, { 16, 1 }, { 26, 1 }, { 27, 6 }, { 28, 15 }, { 29, 20 }, { 30, 15 }, { 31, 6 }, { 32, 1 }, { 57, 1 }, { 58, 7 }, { 59, 21 }, { 60, 35 }, { 61, 35 }, { 62, 21 }, { 63, 7 }, { 64, 1 }, { 120, 1 }, { 121, 8 }, { 122, 28 }, { 123, 56 }, { 124, 70 }, { 125, 56 }, { 126, 28 }, { 127, 8 }, { 128, 1 }, { 247, 1 }, { 248, 9 }, { 249, 36 }, { 250, 84 }, { 251, 126 }, { 252, 126 }, { 253, 84 }, { 254, 36 }, { 255, 9 }, { 256, 1 }, { 502, 1 }, { 503, 10 }, { 504, 45 }, { 505, 120 }, { 506, 210 }, { 507, 252 }, { 508, 210 }, { 509, 120 }, { 510, 45 }, { 511, 10 }, { 512, 1 }, { 1013, 1 }, { 1014, 11 }, { 1015, 55 }, { 1016, 165 }, { 1017, 330 }, { 1018, 462 }, { 1019, 462 }, { 1020, 330 }, { 1021, 165 }, { 1022, 55 }, { 1023, 11 }, { 1024, 1 }, { 2036, 1 }, { 2037, 12 }, { 2038, 66 }, { 2039, 220 }, { 2040, 495 }, { 2041, 792 }, { 2042, 924 }, { 2043, 792 }, { 2044, 495 }, { 2045, 220 }, { 2046, 66 }, { 2047, 12 }, { 2048, 1 }, { 4083, 1 }, { 4084, 13 }, { 4085, 78 }, { 4086, 286 }, { 4087, 715 }, { 4088, 1287 }, { 4089, 1716 }, { 4090, 1716 }, { 4091, 1287 }, { 4092, 715 }, { 4093, 286 }, { 4094, 78 }, { 4095, 13 }, { 4096, 1 }, { 8178, 1 }, { 8179, 14 }, { 8180, 91 }, { 8181, 364 }, { 8182, 1001 }, { 8183, 2002 }, { 8184, 3003 }, { 8185, 3432 }, { 8186, 3003 }, { 8187, 2002 }, { 8188, 1001 }, { 8189, 364 }, { 8190, 91 }, { 8191, 14 }, { 8192, 1 }, { 16369, 1 }, { 16370, 15 }, { 16371, 105 }, { 16372, 455 }, { 16373, 1365 }, { 16374, 3003 }, { 16375, 5005 }, { 16376, 6435 }, { 16377, 6435 }, { 16378, 5005 }, { 16379, 3003 }, { 16380, 1365 }, { 16381, 455 }, { 16382, 105 }, { 16383, 15 }, { 16384, 1 }, { 32752, 1 }, { 32753, 16 }, { 32754, 120 }, { 32755, 560 }, { 32756, 1820 }, { 32757, 4368 }, { 32758, 8008 }, { 32759, 11440 }, { 32760, 12870 }, { 32761, 11440 }, { 32762, 8008 }, { 32763, 4368 }, { 32764, 1820 }, { 32765, 560 }, { 32766, 120 }, { 32767, 16 }, { 32768, 1 }, { 65519, 1 }, { 65520, 17 }, { 65521, 136 }, { 65522, 680 }, { 65523, 2380 }, { 65524, 6188 }, { 65525, 12376 }, { 65526, 19448 }, { 65527, 24310 }, { 65528, 24310 }, { 65529, 19448 }, { 65530, 12376 }, { 65531, 6188 }, { 65532, 2380 }, { 65533, 680 }, { 65534, 136 }, { 65535, 17 }, { 65536, 1 }, { 131054, 1 }, { 131055, 18 }, { 131056, 153 }, { 131057, 816 }, { 131058, 3060 }, { 131059, 8568 }, { 131060, 18564 }, { 131061, 31824 }, { 131062, 43758 }, { 131063, 48620 }, { 131064, 43758 }, { 131065, 31824 }, { 131066, 18564 }, { 131067, 8568 }, { 131068, 3060 }, { 131069, 816 }, { 131070, 153 }, { 131071, 18 }, { 131072, 1 }, { 262125, 1 }, { 262126, 19 }, { 262127, 171 }, { 262128, 969 }, { 262129, 3876 }, { 262130, 11628 }, { 262131, 27132 }, { 262132, 50388 }, { 262133, 75582 }, { 262134, 92378 }, { 262135, 92378 }, { 262136, 75582 }, { 262137, 50388 }, { 262138, 27132 }, { 262139, 11628 }, { 262140, 3876 }, { 262141, 969 }, { 262142, 171 }, { 262143, 19 }, { 262144, 1 }, { 524268, 1 }, { 524269, 20 }, { 524270, 190 }, { 524271, 1140 }, { 524272, 4845 }, { 524273, 15504 }, { 524274, 38760 }, { 524275, 77520 }, { 524276, 125970 }, { 524277, 167960 }, { 524278, 184756 }, { 524279, 167960 }, { 524280, 125970 }, { 524281, 77520 }, { 524282, 38760 }, { 524283, 15504 }, { 524284, 4845 }, { 524285, 1140 }, { 524286, 190 }, { 524287, 20 }, { 524288, 1 }, { 1048555, 1 }, { 1048556, 21 }, { 1048557, 210 }, { 1048558, 1330 }, { 1048559, 5985 }, { 1048560, 20349 }, { 1048561, 54264 }, { 1048562, 116280 }, { 1048563, 203490 }, { 1048564, 293930 }, { 1048565, 352716 }, { 1048566, 352716 }, { 1048567, 293930 }, { 1048568, 203490 }, { 1048569, 116280 }, { 1048570, 54264 }, { 1048571, 20349 }, { 1048572, 5985 }, { 1048573, 1330 }, { 1048574, 210 }, { 1048575, 21 }, { 1048576, 1 }, { 2097130, 1 }, { 2097131, 22 }, { 2097132, 231 }, { 2097133, 1540 }, { 2097134, 7315 }, { 2097135, 26334 }, { 2097136, 74613 }, { 2097137, 170544 }, { 2097138, 319770 }, { 2097139, 497420 }, { 2097140, 646646 }, { 2097141, 705432 }, { 2097142, 646646 }, { 2097143, 497420 }, { 2097144, 319770 }, { 2097145, 170544 }, { 2097146, 74613 }, { 2097147, 26334 }, { 2097148, 7315 }, { 2097149, 1540 }, { 2097150, 231 }, { 2097151, 22 }, { 2097152, 1 }, { 4194281, 1 }, { 4194282, 23 }, { 4194283, 253 }, { 4194284, 1771 }, { 4194285, 8855 }, { 4194286, 33649 }, { 4194287, 100947 }, { 4194288, 245157 }, { 4194289, 490314 }, { 4194290, 817190 }, { 4194291, 1144066 }, { 4194292, 1352078 }, { 4194293, 1352078 }, { 4194294, 1144066 }, { 4194295, 817190 }, { 4194296, 490314 }, { 4194297, 245157 }, { 4194298, 100947 }, { 4194299, 33649 }, { 4194300, 8855 }, { 4194301, 1771 }, { 4194302, 253 }, { 4194303, 23 }, { 4194304, 1 }, { 8388584, 1 }, { 8388585, 24 }, { 8388586, 276 }, { 8388587, 2024 }, { 8388588, 10626 }, { 8388589, 42504 }, { 8388590, 134596 }, { 8388591, 346104 }, { 8388592, 735471 }, { 8388593, 1307504 }, { 8388594, 1961256 }, { 8388595, 2496144 }, { 8388596, 2704156 }, { 8388597, 2496144 }, { 8388598, 1961256 }, { 8388599, 1307504 }, { 8388600, 735471 }, { 8388601, 346104 }, { 8388602, 134596 }, { 8388603, 42504 }, { 8388604, 10626 }, { 8388605, 2024 }, { 8388606, 276 }, { 8388607, 24 }, { 8388608, 1 }, { 16777191, 1 }, { 16777192, 25 }, { 16777193, 300 }, { 16777194, 2300 }, { 16777195, 12650 }, { 16777196, 53130 }, { 16777197, 177100 }, { 16777198, 480700 }, { 16777199, 1081575 }, { 16777200, 2042975 }, { 16777201, 3268760 }, { 16777202, 4457400 }, { 16777203, 5200300 }, { 16777204, 5200300 }, { 16777205, 4457400 }, { 16777206, 3268760 }, { 16777207, 2042975 }, { 16777208, 1081575 }, { 16777209, 480700 }, { 16777210, 177100 }, { 16777211, 53130 }, { 16777212, 12650 }, { 16777213, 2300 }, { 16777214, 300 }, { 16777215, 25 }, { 16777216, 1 }, { 33554406, 1 }, { 33554407, 26 }, { 33554408, 325 }, { 33554409, 2600 }, { 33554410, 14950 }, { 33554411, 65780 }, { 33554412, 230230 }, { 33554413, 657800 }, { 33554414, 1562275 }, { 33554415, 3124550 }, { 33554416, 5311735 }, { 33554417, 7726160 }, { 33554418, 9657700 }, { 33554419, 10400600 }, { 33554420, 9657700 }, { 33554421, 7726160 }, { 33554422, 5311735 }, { 33554423, 3124550 }, { 33554424, 1562275 }, { 33554425, 657800 }, { 33554426, 230230 }, { 33554427, 65780 }, { 33554428, 14950 }, { 33554429, 2600 }, { 33554430, 325 }, { 33554431, 26 }, { 33554432, 1 }, { 67108837, 1 }, { 67108838, 27 }, { 67108839, 351 }, { 67108840, 2925 }, { 67108841, 17550 }, { 67108842, 80730 }, { 67108843, 296010 }, { 67108844, 888030 }, { 67108845, 2220075 }, { 67108846, 4686825 }, { 67108847, 8436285 }, { 67108848, 13037895 }, { 67108849, 17383860 }, { 67108850, 20058300 }, { 67108851, 20058300 }, { 67108852, 17383860 }, { 67108853, 13037895 }, { 67108854, 8436285 }, { 67108855, 4686825 }, { 67108856, 2220075 }, { 67108857, 888030 }, { 67108858, 296010 }, { 67108859, 80730 }, { 67108860, 17550 }, { 67108861, 2925 }, { 67108862, 351 }, { 67108863, 27 }, { 67108864, 1 }, { 134217700, 1 }, { 134217701, 28 }, { 134217702, 378 }, { 134217703, 3276 }, { 134217704, 20475 }, { 134217705, 98280 }, { 134217706, 376740 }, { 134217707, 1184040 }, { 134217708, 3108105 }, { 134217709, 6906900 }, { 134217710, 13123110 }, { 134217711, 21474180 }, { 134217712, 30421755 }, { 134217713, 37442160 }, { 134217714, 40116600 }, { 134217715, 37442160 }, { 134217716, 30421755 }, { 134217717, 21474180 }, { 134217718, 13123110 }, { 134217719, 6906900 }, { 134217720, 3108105 }, { 134217721, 1184040 }, { 134217722, 376740 }, { 134217723, 98280 }, { 134217724, 20475 }, { 134217725, 3276 }, { 134217726, 378 }, { 134217727, 28 }, { 134217728, 1 }, { 268435427, 1 }, { 268435428, 29 }, { 268435429, 406 }, { 268435430, 3654 }, { 268435431, 23751 }, { 268435432, 118755 }, { 268435433, 475020 }, { 268435434, 1560780 }, { 268435435, 4292145 }, { 268435436, 10015005 }, { 268435437, 20030010 }, { 268435438, 34597290 }, { 268435439, 51895935 }, { 268435440, 67863915 }, { 268435441, 77558760 }, { 268435442, 77558760 }, { 268435443, 67863915 }, { 268435444, 51895935 }, { 268435445, 34597290 }, { 268435446, 20030010 }, { 268435447, 10015005 }, { 268435448, 4292145 }, { 268435449, 1560780 }, { 268435450, 475020 }, { 268435451, 118755 }, { 268435452, 23751 }, { 268435453, 3654 }, { 268435454, 406 }, { 268435455, 29 }, { 268435456, 1 }, { 536870882, 1 }, { 536870883, 30 }, { 536870884, 435 }, { 536870885, 4060 }, { 536870886, 27405 }, { 536870887, 142506 }, { 536870888, 593775 }, { 536870889, 2035800 }, { 536870890, 5852925 }, { 536870891, 14307150 }, { 536870892, 30045015 }, { 536870893, 54627300 }, { 536870894, 86493225 }, { 536870895, 119759850 }, { 536870896, 145422675 }, { 536870897, 155117520 }, { 536870898, 145422675 }, { 536870899, 119759850 }, { 536870900, 86493225 }, { 536870901, 54627300 }, { 536870902, 30045015 }, { 536870903, 14307150 }, { 536870904, 5852925 }, { 536870905, 2035800 }, { 536870906, 593775 }, { 536870907, 142506 }, { 536870908, 27405 }, { 536870909, 4060 }, { 536870910, 435 }, { 536870911, 30 }, { 536870912, 1 } };

        public int WaysToReachStair(int k)
        {
            return dial.ContainsKey(k) ? dial[k] : 0;
        }
    }
}
