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

namespace LeetCode.QuestionBank.Question3154
{
    public class Utils3154
    {
        public void Dial()
        {
            Interface3154 solution = new Solution3154();
            for (int i = 0, k; i <= (int)1e9; i++)
            {
                k = solution.WaysToReachStair(i);
                if (k != 0) Console.WriteLine($"{i}, {k}");
            }
        }

        /*
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
         */
    }
}
