Problem Description

Find the number of sequences \( P \) obtained by permuting \( (1, 2, \ldots, N) \) that satisfy the following conditions, and output the result modulo \( 998244353 \).

• For every \( i \) \( (2 \leq i \leq N) \), one of the following holds:
• For all \( j \) \( (1 \leq j < i) \), \( P_j < P_i \)
• For all \( j \) \( (1 \leq j < i) \), \( P_j > P_i \)

Input Format

The input is given from the standard input in the following format:

\( N \)

Output Format

Output the number of sequences \( P \) that satisfy the conditions in the problem statement, modulo \( 998244353 \).

Sample Input and Output

Sample Input #1

2

Sample Output #1

2

Sample Input #2

659636104093210683

Sample Output #2

512716103

Notes/Hints

Constraints

• \( 2 \leq N \leq 10^{18} \)
• \( N \) is an integer

Sample Explanation 1

The sequences obtained by permuting \( (1, 2) \) are \( (1, 2) \) and \( (2, 1) \), both of which satisfy the conditions in the problem statement.

Sample Explanation 2

Output the result modulo \( 998244353 \). Original idea: penguinman

见题面 Input 部分

见题面 Output 部分