타노스는 전통적인 정렬 알고리즘을 좋아하지 않는다.
길이 $m$인 수열 $a_1, a_2, \dots, a_m$에 대해 "타노스 정렬" 연산을 다음과 같이 정의한다:
- 현재 수열이 이미 엄격히 증가하면, 즉 $a_1 < a_2 < \dots < a_m$이면 알고리즘이 즉시 끝난다.
- 그렇지 않으면 현재 수열의 $m$개 위치 중 정확히 $\lfloor m / 2 \rfloor$개를 균등한 확률로 무작위 선택하여 삭제한다. 나머지 원소들의 상대적인 순서를 유지하고, 남은 수열에 같은 과정을 계속 적용한다.
위의 삭제 연산에서 $m$은 초기 길이가 아니라 현재 수열의 길이를 뜻한다. 즉, 어떤 라운드의 시작에 원소가 $m$개 남아 있고 수열이 아직 정렬되지 않았다면, 그 라운드에서는 원소 $\lfloor m / 2 \rfloor$개를 무작위로 삭제한다.
먼저 길이 $N$인 순열 $p_1, p_2, \dots, p_N$을 균등한 확률로 무작위 생성한 뒤, 그 순열에 타노스 정렬을 적용한다.
마지막으로 남은 원소의 개수를 $X$라 하자. $\mathbb{E}[X]$를 구하고, 정답을 $998244353$으로 나눈 나머지를 출력해야 한다.
입력
입력은 한 줄이며, 초기 순열의 길이를 나타내는 정수 $N$ $(1 \le N \le 10^6)$이 주어진다.
출력
$\mathbb{E}[X]$를 $998244353$으로 나눈 나머지를 나타내는 정수 하나를 한 줄에 출력한다.
더 형식적으로, $\mathbb{E}[X]$를 기약분수로 나타내면 $\dfrac{P}{Q}$일 때, $P \cdot Q^{-1} \bmod 998244353$을 출력해야 한다. 여기서 $Q^{-1}$는 모듈로 $998244353$에서의 $Q$의 곱셈 역원이다.
이 문제의 제한 내에서는 위의 역원이 항상 존재함을 증명할 수 있다.
예제
입력 1
2
출력 1
499122178
입력 2
4
출력 2
83187031
참고
- "순열"은 서로 다른 $N$개의 정수 $1, 2, \dots, N$으로 구성된 수열이다.
- 모든 무작위 선택은 가능한 모든 유효한 경우에 대해 균등한 확률로 이루어진다.
- 원소를 삭제해도 남은 원소들의 상대적인 순서는 유지된다.
길이 $2$인 순열은 다음 두 가지뿐이다:
- $[1, 2]$: 이미 정렬되어 있으므로 마지막으로 남는 원소의 개수는 $2$이다.
- $[2, 1]$: 정렬되지 않았으므로 원소 $1$개를 무작위로 삭제해야 한다. 어느 원소를 삭제하더라도 남은 수열의 길이는 $1$이고 반드시 정렬되어 있으므로, 마지막으로 남는 원소의 개수는 $1$이다.
따라서 $\mathbb{E}[X] = \frac{2 + 1}{2} = \frac{3}{2}$이다.
모듈로 $998244353$에서 $\frac{3}{2} \equiv 3 \cdot 2^{-1} \equiv 499122178 \pmod{998244353}.$