問題一覧 > 通常問題

No.1476 esreveR dna esreveR

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 173
作問者 : PCTprobabilityPCTprobability / テスター : 👑 fairy_lettucefairy_lettuce nok0nok0 ygussanyygussany
7 ProblemId : 6050 / 出題時の順位表
問題文最終更新日: 2021-04-11 13:22:08

問題文

$N×N$ の行列があります。この行列の $i$ 行 $j$ 列の値を $a_{i,j}$ とします。

初め、$1 \le i \le N$ を満たす正整数 $i$ に対し、$a_{i,i}=1$ です。それ以外の要素に対しては $a_{i,j}=0\ (i \neq j)$ です。

あなたは以下の操作を好きな順序で $0$ 回以上任意の回数行えます。

  • $1 \le i \le N$ を満たす正整数 $i$ を選び、$i$ 行目を反転させる。より厳密には $1 \le j \le N$ を満たす正整数 $j$ に対して $a_{i,j}$ を $a_{i,N-j+1}$ に置き換える。
  • $1 \le j \le N$ を満たす正整数 $j$ を選び、$j$ 列目を反転させる。より厳密には $1 \le i \le N$ を満たす正整数 $i$ に対して $a_{i,j}$ を $a_{N-i+1,j}$ に置き換える。

最終的に作ることが可能な行列の個数を求めてください。

ただし、解はとても大きくなることがあるので $998244353$ で割った余りを求めてください。

入力

$N$

  • 入力は全て整数である。
  • $1 \le N \le 10^{18}$

出力

最終的に作ることが可能な行列の個数を求めてください。

ただし、解はとても大きくなることがあるので $998244353$ で割った余りを求めてください。

サンプル

サンプル1
入力
2
出力
6

初め、行列は以下のようになっています。

1 0
0 1

$N=2$ の時は $0,1$ をそれぞれ $2$ 個要素に持つような行列は全て作ることができ、それ以外は作ることが出来ないため $6$ を出力してください。

例えば、$1$ 行目を反転させることにより以下の行列を得ることが出来ます。

0 1
0 1

サンプル2
入力
2021
出力
654946506

$998244353$ で割った余りを出力してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。