1269. Number of Ways to Stay in the Same Place After Some Steps Hard

1/**
2 * [1269] Number of Ways to Stay in the Same Place After Some Steps
3 *
4 * You have a pointer at index 0 in an array of size arrLen. At each step, you can move 1 position to the left, 1 position to the right in the array, or stay in the same place (The pointer should not be placed outside the array at any time).
5 * Given two integers steps and arrLen, return the number of ways such that your pointer still at index 0 after exactly steps steps. Since the answer may be too large, return it modulo 10^9 + 7.
6 *  
7 * Example 1:
8 * 
9 * Input: steps = 3, arrLen = 2
10 * Output: 4
11 * Explanation: There are 4 differents ways to stay at index 0 after 3 steps.
12 * Right, Left, Stay
13 * Stay, Right, Left
14 * Right, Stay, Left
15 * Stay, Stay, Stay
16 * 
17 * Example 2:
18 * 
19 * Input: steps = 2, arrLen = 4
20 * Output: 2
21 * Explanation: There are 2 differents ways to stay at index 0 after 2 steps
22 * Right, Left
23 * Stay, Stay
24 * 
25 * Example 3:
26 * 
27 * Input: steps = 4, arrLen = 2
28 * Output: 8
29 * 
30 *  
31 * Constraints:
32 * 
33 * 	1 <= steps <= 500
34 * 	1 <= arrLen <= 10^6
35 * 
36 */
37pub struct Solution {}
38
39// problem: https://leetcode.com/problems/number-of-ways-to-stay-in-the-same-place-after-some-steps/
40// discuss: https://leetcode.com/problems/number-of-ways-to-stay-in-the-same-place-after-some-steps/discuss/?currentPage=1&orderBy=most_votes&query=
41
42// submission codes start here
43
44impl Solution {
45    pub fn num_ways(steps: i32, arr_len: i32) -> i32 {
46        0
47    }
48}
49
50// submission codes end
51
52#[cfg(test)]
53mod tests {
54    use super::*;
55
56    #[test]
57    fn test_1269() {
58    }
59}
60