Colin은 최근 Eva로부터 신비로운 오름차순 난수 수열 생성기를 선물로 받았습니다! 양의 정수 $n$을 입력하기만 하면, 생성기가 오름차순 수열을 반환합니다! 반복된 실험 끝에 Colin은 생성기가 어떻게 작동하는지 알아냈습니다.

처음에 생성기는 새로운 빈 수열을 생성하고, $\{1, 2, \cdots, n\}$에서 동일한 확률로 수 $k$를 선택합니다.

그 다음, 생성기는 수열의 첫 번째 원소로 $\{1, 2, \cdots, n\}$에서 동일한 확률로 수 $x$를 선택합니다.

그 후 생성기는 다음 과정을 반복합니다:

• 수열의 최댓값이 $k$ 이상이면, 생성기는 즉시 작동을 멈추고 이미 생성된 현재 수열을 반환합니다.
• 그렇지 않고 수열의 최댓값이 $y$이면, 생성기는 $\{y + 1, y + 2, \cdots, n\}$에서 동일한 확률로 수 $x$를 선택하여 수열의 끝에 $x$를 추가합니다.

이제 Colin은 주어진 $n$에 대해 생성기가 반환하는 수열 길이의 기댓값이 얼마인지 알고 싶습니다.

입력

단일 정수 $n$ ($1 \le n \le 10^7$).

출력

길이의 기댓값을 $998244353$으로 나눈 나머지를 나타내는 단일 정수를 출력합니다.

예제

입력 1

3

출력 1

55458021

참고

• $k = 1$인 경우, 기대 길이는 $1$입니다.
• $k = 2$인 경우, 기대 길이는 $1 \times \frac{2}{3} + 2 \times \frac{1}{3} = \frac{4}{3}$입니다.
• $k = 3$인 경우, 기대 길이는 $1 \times \frac{1}{3} + 2 \times (\frac{1}{3} + \frac{1}{3} \times \frac{1}{2}) + 3 \times \frac{1}{3} \times \frac{1}{2} = \frac{11}{6}$입니다.

따라서 정답은 $(1 + \frac{4}{3} + \frac{11}{6})/3 = \frac{25}{18}$입니다.

$18$의 $998244353$에 대한 모듈러 역원은 $720954255$이므로, 출력 결과는 $25 \times 720954255 \bmod 998244353 = 55458021$입니다.