This problem can be Dynamic Programming (DP). In this editorial, we will explain two ways to solve it.

In the following editorial, we call an integer “a flat number” if each digit is between \(1\) and \(9\) (inclusive) and the difference between every adjacent pair of digits is at most \(1\).

Method 1: Design DP by writing down the recurrence relations

For example, we consider the first Sample. How many four-digit flat numbers are there?

Let’s divide them by cases to count them.
There are many ways of case division; one natural way is to divide them depending on the first digit.
For instance, what if the first digit is \(7\)?

\(7???\)

In this case, we want to find how many ways are there to fill the last three digits to make the entire integer a flat number. Let’s denote the answer by \(f(7???)\).

It’s still difficult to find. So let’s divide them by cases again.
A natural idea is to consider the second digit. By the condition, the second digit should be either \(6\), \(7\), or \(8\).

\(76??\)
\(77??\)
\(78??\)

That is, \(f(7???) = f(76??) + f(77??) + f(78??)\).

Here, the number of ways to fill \(?\)’s in \(76??\) so that it results in a flat number is equal to the number of ways to fill \(?\)’s in \(6??\) so that it results in a flat number. (The leading \(7\) in \(76??\) does not affect to \(?\)’s to be filled.) So we have

\(f(76??) = f(6??)\).

Together with the observation above, we obtain a simple recurrence relation of \(f\):

\(f(7???) = f(6??) + f(7??) + f(8??)\).

We will now apply this recurrence relation repeatedly. For example, when we want the value of \(f(6??)\) to obtain the right hand side of the equation above, we can use the following equation:

\(f(6??) = f(5?) + f(6?) + f(7?)\)

which can be obtained by the similar way as before. Note that, when repeating in this way, the argument of \(f\) is always a single-digit integer followed by \(?\)’s.
Now, let’s find the values of \(f\) for all the arguments of that form.

Prepare a two-dimensional array \(dp[][]\). The value of \(dp[n][k]\) is the value of \(f(k??? \dots???)\) (where the argument is a string consisting of \(k\) followed by \(n-1\) copies of \(?\)). For example, \(dp[4][7] = f(7???)\). By the recurrence relation we obtained before, we have \(dp[4][7] = dp[3][6] + dp[3][7] + dp[3][8]\).

How to fill the array with correct values?
For example, in order to find \(dp[4][7]\), we should already know the correct values of \(dp[3][6], dp[3][7]\), and \(dp[3][8]\).
In this case, it is sufficient to fill them in the increasing order of n. (Note that we should be careful enough of the order of filling the array.)

Specifically, we can implement as follows.

• For \(n = 1, 1 \le k \le 9\), let \(dp[n][k] = 1\).
• Next, iterate \(n\) for \(2\) and greater in the increasing order to fill \(dp[n][k]\).
  • For example, let \(dp[4][7] = dp[3][6] + dp[3][7] + dp[3][8]\).

Note when implementing the special case for \(k = 1\) and \(k = 9\). For more details, please refer to the sample code at the bottom of the editorial.

Method 2: Derive the solution from enumeration of flat numbers

First, let us consider how to enumerate all \(N\)-digit flat numbers.
Let \(list[D][r]=\) (the set of \(D\)-digit flat numbers ending with \(r\)), which we will find in the increasing order of \(D\).

Obviously, \(list[1][i]=\{i\}\), so we will start from here.
We will consider obtaining \(list[D+1]\) from \(list[D]\) by appending a digit to each element.
Clearly, if “\(X\) is a \((D+1)\)-digit flat number”, then “the first \(D\) digits of \(X\) forms a flat number.” That’s why each element of \(list[D+1]\) can be obtained by appending a digit to an element of \(list[D]\). We can also see that a \(D\)-digit flat number succeeded by a digit becomes a \((D+1)\)-digit flat number if and only if the difference between the final digit of the \(D\)-digit flat number and the digit to be appended is at most \(1\).
Therefore, what we have to do is as follows.

• For each integer \(1 \le i \le 9\), do the following operation.
  • For each integer \(\max(1,i-1) \le j \le \min(9,i+1)\), do the following operation.
  • For every element \(E\) in \(list[D][i]\), add \(E\) succeeded by \(j\) to \(list[D+1][j]\).

For example, we have \(list[2][9]=\{89,99\}\), so we will add to \(list[3][8]\) every element of \(list[2][9]\) succeeded by \(8\), that is, \(\{898,998\}\). This kind of operations are done in the increasing order of \(D\).
The set of \(N\)-digit flat numbers is entire \(list[N]\).
Here, obviously but importantly, if the elements of \(list[D]\) are pairwise distinct, then those of \(list[D+1]\) are pairwise distinct too.
Therefore, we could enumerate all the flat numbers exhaustively without duplicates.

However, we cannot store all the elements of the sets, both in terms of space complexity and time complexity, so we will find only the number of integers satisfying the conditions instead.

Let us consider computing \(dp[D][r]=\) (the number of \(D\)-digit flat numbers ending with \(r\)) one by one.
This can be obtained in the same way as before, but instead of enumerating each element, we only have to count the numbers. It is essentially the same as the generation of \(list\), so we will omit the details (please refer to the sample code).

Note that you have to find the answer modulo \(998244353\). This can be achieved by computing the remainder of each \(dp\) divided by \(998244353\).

Sample code (C++):

#include<bits/stdc++.h>
#define mod 998244353

using namespace std;

int dp[1048576][10]={0};

int main(){
  int n;
  cin >> n;
  for(int i=1;i<=9;i++){dp[1][i]=1;}
  for(int d=2;d<=n;d++){
    for(int i=1;i<=9;i++){
      for(int j=max(1,i-1);j<=min(9,i+1);j++){
        dp[d][j]+=dp[d-1][i];
        dp[d][j]%=mod;
      }
    }
  }
  int res=0;
  for(int i=1;i<=9;i++){
    res+=dp[n][i];
    res%=mod;
  }
  cout << res << '\n';
  return 0;
}