GCD Invariance in 7-9 Strings

We call a pair of strings \( (S, T) \) an indistinguishable pair if they satisfy all of the following conditions:

• Both \( S \) and \( T \) are strings of length \( n \) consisting only of the digits 7 and 9.
• \( S \) is lexicographically smaller than \( T \) (i.e. \( S < T \)).
• For every two distinct intervals \( [l_1, r_1] \) and \( [l_2, r_2] \) with \(1 \le l_1 \le r_1 \le n\) and \(1 \le l_2 \le r_2 \le n\) (the intervals are different), let
  \( A_S \) be the decimal number obtained by concatenating the digits of \( S \) from position \( l_1 \) to \( r_1 \), and \( B_S \) be the decimal number from positions \( l_2 \) to \( r_2 \); similarly define \( A_T \) and \( B_T \) for \( T \).
  It must hold that \[ \gcd(A_S, B_S) = \gcd(A_T, B_T). \] All formulas are in \( \LaTeX \) format.

It can be shown that, due to the strong restrictions imposed by the gcd condition over all possible pairs of intervals, an indistinguishable pair \( (S, T) \) exists only in very limited cases. In fact, a careful analysis of the condition on single-digit intervals (which are valid intervals since every interval of the form \([i,i]\) is allowed) reveals that if there exist two distinct indices \( i \) and \( j \) such that \( S_i = S_j \) then the corresponding digits in \( T \) must also be equal. Since \( S \) and \( T \) cannot be identical (because \( S < T \)), the only possibility is that both strings have no repeated digit. However, since each string is formed only by the digits \( 7 \) and \( 9 \), it is impossible to form a string of length \( n \ge 3 \) without a repetition. (For example, in any string of length 3 there must be at least two positions carrying the same digit.)

Therefore, the only possible cases occur when \( n = 1 \) or \( n = 2 \). In the case \( n = 1 \), the only possible pair is \( S = 7 \) and \( T = 9 \). In the case \( n = 2 \), the only valid non-repeating string is \( S = 79 \) (thus forcing \( T = 97 \) to have the complementary pattern) and it can be verified that \( (79, 97) \) indeed satisfies the condition. For \( n \ge 3 \), no valid pair exists.

Your task is to compute the number of indistinguishable pairs \( (S, T) \) among all pairs of strings of length \( n \) (formed by digits \( 7 \) and \( 9 \)) that satisfy the above conditions, and output the answer modulo \( 998244353 \).

Input Format: A single integer \( n \) is given.

Output Format: Output one integer, the number of indistinguishable pairs modulo \( 998244353 \).

inputFormat

The input consists of a single line containing one integer \( n \) (\( 1 \le n \le 10^9 \), though by the problem observation only \( n=1 \) or \( n=2 \) yield a positive answer).

outputFormat

Output a single integer, the number of indistinguishable pairs \( (S, T) \) modulo \( 998244353 \).

sample

1

1