問題一覧 > 通常問題

No.1755 Almost Palindrome

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 40
作問者 : NyaanNyaanNyaanNyaan / テスター : PCTprobabilityPCTprobability tokusakuraitokusakurai
1 ProblemId : 7118 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-11-20 20:46:55

問題文

次の条件を満たす文字列 $S$ を「ほぼ回文」と呼びます。

  • $S$ は a から z までの英小文字からなる文字列である。
  • $S$ は回文ではない。
  • $S$ から $i$ 文字目を取り除いたものが回文になるような $i\ (1 \leq i \leq |S|)$ が存在する。

例えば、 $S = $ nyaan とすると、$S$ は回文ではないですが、2文字目の y を取り除いた naan は回文なので $S$ は「ほぼ回文」です。

$N$ が与えられるので、長さ $N$ の「ほぼ回文」の個数を $998244353$ で割ったあまりを求めてください。

テストケースは $T$ 個与えられるので、それぞれについて答えを求めてください。

制約

  • 入力は全て整数である。
  • $1 \leq T \leq 10^5$
  • $1 \leq N \leq 10^6$

入力

入力は次の形で与えられます。
$T$
$\mathrm{case}1$
$\vdots$
$\mathrm{case}T$
各ケースは次の形で与えられます。
$N$

出力

$T$ 行出力して最後に改行してください。
$i$ 行目には $i$ 番目のテストケースに対する答えを出力してください。

サンプル

サンプル1
入力
5
1
2
3
100
133333
出力
0
650
1300
81960607
708231776

長さ $1$ の「ほぼ回文」は明らかに $0$ 個です。
長さ $2$ の「ほぼ回文」は $1$ 文字目と $2$ 文字目の文字が異なる長さ $2$ 文字列の個数に等しく、 $26 \times 25 = 650$ 個あります。

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