According to the question, since we can only press the button to the left, right, top and bottom of the current button and the current button itself, therefore, after pressing 0, we can only press {0,8}, after pressing 1, we can only press {1,2,4}, after pressing 2 we can only press {1,2,3,5}, after pressing 3 we can only press{2,3,6} and so on.

Now, we make 2D arrays for different situations.

In each cell of the following 2d arrays we store the number of words that can be obtained if the corresponding key is pressed at last.

• Let N=1. This denotes that one button can be pressed on the keypad.

Since N=1 and only one key can be pressed, therefore for each key only 1 word can be formed which is the number on the key itself.

This means, if we press key 1, then the one word formed is "1", if we press key 2, then the one word formed is "2", if we press 3, then the one word formed is "3" and so on.

• Let N=2. This denotes that at a time 2 buttons can be pressed on the keyboard.

The number of words of size 2 (as 2 buttons can be pressed) such that the button pressed at last is:

Button 1: 3 words {1-1, 2-1 and 4-1}

Button 2: 4 words {1-2, 2-2, 5-2 and 3-2}

Button 3: 3 words {2-3, 3-3 and 6-3}

Button 4: 4 words {1-4, 4-4, 5-4 and 7-4}

Button 5: 5 words {2-5, 4-5, 5-5, 6-5 and 8-5}

And so on.

• For N=3, the total number of buttons that can be pressed are 3.

The number of words of size 3 (as 3 buttons can be pressed) such that the button pressed at last is:

Button 1: 11 words i.e. the sum of words for buttons 1, 2 and 4 in N=2 i.e. 3+4+4.

We simply add button 1 to the last of all the words for buttons 1, 2 and 4 in N=2.

Button 1 {1-1-1, 2-1-1 and 4-1-1}, Button 2 {1-2-1, 2-2-1, 5-2-1 and 3-2-} and Button 4{1-4, 4-4, 5-4 and 7-4}.

Button 2: 15 words= 3+4+3+5 (refer to figure 3)

Button 3: 11 words= 4+3+4 (refer to figure 3)

Button 4: 15 words= 3+4+5+3 (refer to figure 3)

And so on.

Now, if you have understood the above explanation, we can now make a single DP array for all these values of N.

In figure, the rows represent the values of N i.e. the number of buttons that can be pressed and the columns represent all the buttons from 0-9.

At each cell we store the number of words that can be formed for the corresponding value of N such that the corresponding button is pressed at last.

• As we already know, for N=0, i.e. when no button is pressed, 0 words can be formed.
• Also, if for N=1, if only one button is to be pressed, then we can form only 1 word for each button which is the number on the button itself.
• If N=2, then for:
1. Button 0: 2 words=1+1 i.e. (words for button 0 in N=1 + words for button 8 in N=1)
2. Button 1: 3 words=1+1+1 i.e. (words for button 1 in N=1 + words for button 2 in N=1 + words for button 4 in N=1)

And so on.

• If N=3, then for:
1. Button 0: 7 words=2+5 i.e. (words for button 0 in N=2 + words for button 8 in N=2)
2. Button 1: 11=3+4+4 i.e. (words for button 1 in N=2 + words for button 2 in N=2 + words for button 4 in N=2)
3. Button 2: 15=3+4+3+5 i.e. (words for button 1 in N=2 + words for button 2 in N=2 + words for button 3 in N=2 + words for button 5 in N=2)

And so on.

Hence we print the sum of words of all the buttons from 0-9 for the given input N. For example, if N=2, then 2+3+4+3+4+5+4+3+5+3=36 is printed.