Distinct Remainders

Alice and Bob enjoy relaxing by dining at various food stalls. There are n restaurants on the food street. The i-th restaurant costs i dollars to dine in. Given a budget a (an integer such that 2 ≤ a ≤ n), Alice can choose any restaurant among the first a ones.

To decide which restaurant to go to, Alice pre-selects a nonnegative integer k with k < \(\mathrm{lcm}_{i=1}^{n} i\). When the budget a is revealed, she chooses the restaurant number \((k \bmod a) + 1\).

However, Alice wants to change her dining taste every time. In other words, for every possible budget a with 2 ≤ a ≤ n, the selected restaurant (which is determined by \((k \bmod a) + 1\)) should be different. Formally, for a given n, count the number of integers \(k \in \left[0,\,\mathrm{lcm}_{i=1}^{n} i\right)\) such that the set \(\{ k \bmod 2,\; k \bmod 3,\; \dots,\; k \bmod n \}\) contains n − 1 distinct values.

It can be shown by the Chinese Remainder Theorem that every tuple \((k \bmod 2, k \bmod 3, \dots, k \bmod n)\) uniquely occurs when \(k\) runs in the specified range, and hence the problem reduces to counting the number of sequences \((r_2, r_3, \dots, r_n)\) with \(r_a \in \{0, 1, \dots, a-1\}\) that are pairwise distinct. Note that for any \(a \ge 3\), the previously chosen remainders \(r_2, \dots, r_{a-1}\) are all less than \(a\) (in fact, they are in \(\{0,1,\ldots,a-2\}\)). Thus, for each a from 3 to n, there are exactly 2 choices for \(r_a\) (since out of \(a\) possibilities, exactly \(a-2\) are already taken). For a=2, there are 2 choices. Overall, the total number of valid sequences is \[ 2\times 2^{n-2} = 2^{n-1}. \] Since the answer can be huge, output it modulo 998244353.

inputFormat

The input consists of a single integer n (with n ≥ 2).

outputFormat

Output one integer: the number of valid integers k modulo 998244353.

sample

2

2