Adjacent Transpositions Game

Aob and Blice are playing a strange game with a permutation \( p \) of length \( n \). Initially, both players have an empty set \( S_A \) and \( S_B \) (which do not allow duplicates). The game is played in rounds as follows:

• Aob randomly selects two indices \( x, y \) (with \( 1 \le x p_y \) (i.e. an inversion is formed). Then, from the two ordered pairs \( (x,y) \) and \( (p_x,p_y) \), he picks one uniformly at random and adds it to his set \( S_A \).
• After that, using the same indices \( x,y \) chosen by Aob, Blice chooses one ordered pair from \( (y,x) \) and \( (p_y,p_x) \) and adds it to his set \( S_B \>.

The players repeat the rounds infinitely many times. We say that Blice can force a tie if, for every \( \varepsilon >0 \), there exists a positive integer \( N \) such that for all \( n > N \), Blice has a strategy to ensure that after \( n \) rounds the probability that \( S_A \) and \( S_B \) are not identical is less than \( \varepsilon \). In other words, with a proper strategy, Blice can guarantee that ultimately \( S_A = S_B \) with probability arbitrarily close to 1.

It turns out that Blice wants the final sets to be equal. Although Aob plays completely at random, Blice can plan his moves in advance, but only if the original permutation \( p \) has a very special structure. Some numbers in the permutation have disappeared, so Blice asks you to count the number of possible original permutations \( p \) (of \( \{1,2,\dots,n\} \)) such that it is possible to force a tie under the rules of the game.

After a careful analysis, one can prove that for the tie to be forced, every inversion \( (x,y) \) (i.e. every pair with \( x p_y \)) must satisfy

[ p_x = y \quad \text{and} \quad p_y = x. ]

This means that if indices \( x \) and \( y \) form an inversion, then they must form a 2-cycle (a transposition) in \( p \). Moreover, if a 2-cycle \( (x,y) \) occurs, there cannot be any fixed point or another 2-cycle index lying strictly between \( x \) and \( y \); in other words, every 2-cycle must occur on two consecutive indices. The remainder of the elements must be fixed points (i.e. \( p_i = i \)).

Therefore, the valid permutations are exactly those obtained by taking the identity permutation \( [1,2,\dots,n] \) and choosing some disjoint adjacent pairs to swap. For example, when \( n = 4 \), the valid permutations are:

• The identity: \( [1,2,3,4] \).
• Swap positions 1 and 2: \( [2,1,3,4] \).
• Swap positions 2 and 3: \( [1,3,2,4] \).
• Swap positions 3 and 4: \( [1,2,4,3] \).
• Swap positions 1 and 2, and positions 3 and 4: \( [2,1,4,3] \).

Notice that the number of ways to select disjoint adjacent swaps in a line of \( n \) items is well known to be equal to the \( n\text{th} \) term in the recurrence

[ f(0)=1, \quad f(1)=1, \quad f(n)=f(n-1)+f(n-2) \text{ for } n\ge2. ]

Equivalently, it is the \( (n+1)\)th Fibonacci number (with \( F_0 = 0 \) and \( F_1=1 \)).

Your task is: Given an integer \( n \), compute the number of valid permutations \( p \) modulo \( 998244353 \).

inputFormat

The input consists of a single integer \( n \) (\( 1 \le n \le 10^6 \) or as specified by the problem constraints).

outputFormat

Output the number of valid permutations modulo \( 998244353 \).

sample

1

1