/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
0 以上 2^N 未満の非負整数からなる集合 S のうち、以下の条件を満たすものの個数を 998244353 で割ったあまりを出力してください。
- S の空でない部分集合 T は以下のどちらかを満たす。
- T の要素数が奇数
- T の全要素の \mathrm{XOR} が 0 でない
\mathrm{XOR} とは
非負整数 A, B のビット単位 \mathrm{XOR} 、A \oplus B は、以下のように定義されます。
- A \oplus B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
一般に k 個の整数 p_1, p_2, p_3, \dots, p_k のビット単位 \mathrm{XOR} は (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k) と定義され、これは p_1, p_2, p_3, \dots p_k の順番によらないことが証明できます。
制約
- 1 \le N \le 2 \times 10^5
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを出力せよ。
入力例 1
2
出力例 1
15
\lbrace 0,2,3 \rbrace や \lbrace 1 \rbrace や \lbrace \rbrace は条件を満たします。
\lbrace 0,1,2,3 \rbrace は条件を満たしません。
なぜなら、\lbrace 0,1,2,3 \rbrace は部分集合 \lbrace 0,1,2,3 \rbrace が要素数が偶数であり、全要素の \mathrm{XOR} が 0 であるからです。
入力例 2
146
出力例 2
743874490
Score : 600 points
Problem Statement
How many sets S consisting of non-negative integers between 0 and 2^N-1 (inclusive) satisfy the following condition? Print the count modulo 998244353.
- Every non-empty subset T of S satisfies at least one of the following:
- The number of elements in T is odd.
- The \mathrm{XOR} of the elements in T is not zero.
What is \mathrm{XOR}?
The bitwise \mathrm{XOR} of non-negative integers A and B, A \oplus B, is defined as follows:
- When A \oplus B is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if exactly one of the digits in that place of A and B is 1, and 0 otherwise.
Generally, the bitwise \mathrm{XOR} of k non-negative integers p_1, p_2, p_3, \dots, p_k is defined as (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k). We can prove that this value does not depend on the order of p_1, p_2, p_3, \dots, p_k.
Constraints
- 1 \le N \le 2 \times 10^5
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
Output
Print the answer.
Sample Input 1
2
Sample Output 1
15
Sets such as \lbrace 0,2,3 \rbrace, \lbrace 1 \rbrace, and \lbrace \rbrace satisfy the condition.
On the other hand, \lbrace 0,1,2,3 \rbrace does not.
This is because the subset \lbrace 0,1,2,3 \rbrace of \lbrace 0,1,2,3 \rbrace has an even number of elements, whose bitwise \mathrm{XOR} is 0.
Sample Input 2
146
Sample Output 2
743874490