# Mike and Mobile

#### Mike is a little boy who loves solving math problems. One day he was playing with his mom’s mobile. The mobile keypad contains 12 buttons { 10 digits(0-9) and 2 characters(‘*’ and ‘#’) }. Mike wants to know how many different numbers he can generate after pressing exactly the 'N' buttons on the keypad. Mike presses the buttons with the following rules:

```
1. He always presses the button which has a digit written on it, i.e., he never presses the ‘*’ and ‘#’ button.
2. Once he presses a button, the next button he presses should either be the same button or the button which is adjacent to the previous button.
3. In starting he can press any button except ‘*’ and ‘#’.
```

#### Mike is too little to solve this problem. Help Mike to solve this problem. As the answer can be large, so find the answer modulo 10^9 + 7.

##### Input format :

```
The first line of input contains a single integer 'T', representing the number of test cases or queries to be run.
Then the 'T' test cases follow.
The first and only line of each test case contains a positive integer N, which represents the number of buttons to press.
```

##### Output Format :

```
For each test case, print the number of numbers that can be generated after pressing exactly the N buttons on the keypad.
The output of each test case is printed in a separate line.
```

##### Note:

```
You do not need to print anything, it has already been taken care of. Just implement the given function.
```

##### Constraints :

```
1 <= T <= 10
1 <= N <= 5 * 10^4
Time Limit: 1 sec
```

We will recursively find the different numbers we can generate after pressing N buttons on the keypad.

For simplicity, we will define the keypad with a 2D matrix.

keypad[][] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}, {-1, 0, -1}}

**Below is the detailed algorithm:**

Make a recursive function ‘generateNumbersHelper’ which will return the number of numbers we can generate after pressing ‘N’ buttons on the ‘KEYPAD’.

- Call the function: generateNumbersHelper('COUNT', ‘PREV’), where ‘COUNT’ denotes the number of buttons pressed and ‘PREV’ denotes the previous button pressed.
- If 'COUNT' is equal to ‘N’, return 1.
- Make a variable ‘ANS’ which stores the count of different numbers we can generate after pressing ('N' - 'COUNT') buttons on the ‘KEYPAD’. Initialise ‘ANS’ with 0.
- Check every possible button which we can press in the current state.
- Let ‘R’ denote the row of ‘PREV’ in the ‘KEYPAD’ matrix and ‘C’ denote the column of ‘PREV’ in the ‘KEYPAD’ matrix.
- There are at most 5 possibilities, { ('R', 'C'), ('R'-1, 'C'), ('R'+1, 'C'), ('R', 'C'-1), ('R', ‘C’+1)}.
- Let’s say we press the button with index ('X', ‘Y’), then ('X', 'Y') must be inside the ‘KEYPAD’ matrix and ‘KEYPAD[X][Y]’ must not be equal to -1.
- Update the ‘ANS’, ‘ANS’ += generateNumbersHelper('COUNT'+1, 'KEYPAD[X][Y]').

- Return the ‘ANS’.

In the previous approach, we are recalculating the answer. We can optimise it by storing the answers which we have calculated.

For example:

Consider the same recursive function, used in the previous approach.

Function: generateNumbersHelper('COUNT', ‘PREV’), where ‘COUNT’ denotes the number of buttons pressed and ‘PREV’ denotes the previous button pressed.

We are recalculating the answer for {(6,1) and (6,5)}.

So since there are overlapping solutions, we can store the solution which we have calculated. For this, we will make a 2D array, ‘DP’ to store the answer.

‘DP[COUNT][PREV]’ denotes the number of different numbers we can generate after pressing ('N'-count) buttons on the ‘KEYPAD’ and ‘PREV’ is ('COUNT'-1)th button that we have pressed.

**Below is the detailed algorithm:**

Make a recursive function ‘generateNumbersHelper’ which will return the number of numbers we can generate after pressing ‘N’ buttons on the ‘KEYPAD’.

- Make a 2D ‘DP’ array of size ‘N*10', and initialize it with -1.
- Call the function: generateNumbersHelper('COUNT', ‘PREV’), where ‘COUNT’ denotes the number of buttons pressed and ‘PREV’ denotes the previous button pressed.
- If 'COUNT' is equal to ‘N’, return 1.
- If we have visited this state, i.e, ‘DP[COUNT][PREV]’ != -1, then return ‘DP[COUNT][PREV]’.
- Make a variable ‘ANS’ which stores the count of different numbers we can generate after pressing ('N' - 'COUNT') buttons on the ‘KEYPAD’. Initialize ‘ANS’ with 0.
- Check every possible button which we can press in the current state.
- Let ‘R’ denote the row of ‘PREV’ in the ‘KEYPAD’ matrix and ‘C’ denote the column of ‘PREV’ in the ‘KEYPAD’ matrix.
- There are at most 5 possibilities, { ('R', 'C'), ('R'-1, 'C'), ('R'+1, 'C'), ('R', 'C'-1), ('R', ‘C’+1)}.
- Let’s say we press the button with index ('X', ‘Y’), then ('X', 'Y') must be inside the ‘KEYPAD’ matrix and ‘KEYPAD[X][Y]’ must not be equal to -1.
- Update the ‘ANS’, ‘ANS’ += generateNumbersHelper('COUNT'+1, 'KEYPAD[X][Y]').

- Update ‘DP[COUNT][PREV]’, ‘DP[COUNT][PREV]’ = ‘ANS’.
- Return the ‘ANS’.

**Below is the detailed algorithm:**

- Create a 2D array ‘DP’ of size (‘N’+1) * 10 to store the answer.
- Here, ‘DP[COUNT][PREV]’ denotes the number of different numbers we can generate after pressing ‘COUNT’ buttons on the keypad and ‘PREV’ is (‘COUNT’-1)th button that we have pressed.

- Run a loop from 0 to 9 (say iterator = ‘i’):
- Initialize ‘DP[1][i]’ = 1 (Because we will get only 1 number (which will be equal to ‘i’)).

- Initialise all other values with 0.
- Now, iterate on the indices from 2 to N (say iterator = ‘i’):
- Iterate on the digits from 0 to 9 (say iterator = ‘j’):
- Initialise ‘DP[i][j]’ with 0.
- Now iterate on the digits that are adjacent to ‘j’.
- Update ‘DP[i][j]’ :
- ‘DP[i][j]’ += ‘DP[(i-1)][X]’ (where ‘X’ denotes the digits which are adjacent to ‘j’).

- Finally, return sum of { ‘DP[N][0]’ to ‘DP[N][9’] } as the answer.

In the previous approach, we create a 2D array ‘DP’ of size (‘N’+1) * 10 to store the answer.

But, for calculating the answers for ‘DP[i][0 to 9]’, we only need values of ‘DP[i-1][0 to 9]’.

Parity of ‘i’ and (‘i-1’) will always be different i.e. if ‘i’ is odd, (‘i-1’) will be even and vice-versa. So, instead of storing the answer of ‘DP[i][j]’, we can store the answer for ‘DP[parity of i][j]’.

It means we can optimize the space by creating the ‘DP’ array of size 2 * 10.

**Below is the detailed algorithm:**

- Create integer array ‘DP’ of size 2 * 10.
- Run a loop from 0 to 9 (say iterator = ‘i’):
- Initialize ‘DP[1][i]’ = 1 (Because we will get only 1 number (which will be equal to ‘i’)).

- Now, iterate on the indices from 2 to N (say iterator = ‘i’):
- Iterate on the digits from 0 to 9 (say iterator = ‘j’):
- Initialise ‘DP[i%2][j]’ with 0.
- Now iterate on the digits that are adjacent to ‘j’.
- Update ‘DP[i%2][j]’ :
- ‘DP[i%2][j]’ += ‘DP[(i-1)%2][X]’ (where ‘X’ denotes the digits which are adjacent to ‘j’).

- Finally, return sum of { ‘DP[N%2][0]’ to ‘DP[N%2][9]’ } as the answer.