問題一覧 > 通常問題

No.2529 Treasure Hunter

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 94
作問者 : PCTprobabilityPCTprobability / テスター : NyaanNyaanNyaanNyaan
3 ProblemId : 7174 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-11-03 22:15:19

問題文

PCT 君は M×NM \times N のグリッドで構築される世界の創造神になりました。

以下、上から ii 番目、左から jj 番目のマスを (i,j)(i,j) と呼ぶことにします。

この世界に、以下の条件を全て満たすようにいくつかのマスを選び秘宝を埋めることにしました。

  • 各マスには秘宝は高々 11 個までしか埋められない。
  • 各行の内秘宝は高々 22 個までしか埋められない。
  • 秘宝が埋められているマスは隣り合ってはならない。ただし、この世界では (i,1)(i,1)(i,N)(i,N) は隣り合っているものとする。

条件を満たす秘宝の埋め方を 998244353998244353 で割ったあまりを求めてください。

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

制約

  • 入力は全て整数である。
  • 1T2×1051 \le T \le 2 \times 10^5
  • 2N,M2×1052 \le N,M \le 2 \times 10^5
  • テストケースの NN の総和は 2×1052 \times 10^5 以下である。
  • テストケースの MM の総和は 2×1052 \times 10^5 以下である。

入力

入力は以下の形式で与えられます。

TT
case1\mathrm{case}1
\vdots
caseT\mathrm{case}T

各ケースは次の形で与えられます。

N MN\ M

出力

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

サンプル

サンプル1
入力
5
4 2
5 6
123 456
1234 5678
3141 5926
出力
35
276561
532350908
204920481
830272369

始めのテストケースに対しては、例えば以下の図 11 のような配置が条件を満たします。図 22(2,1)(2,1)(2,4)(2,4) は両方秘宝が置かれていますが隣り合っているため不適切です。

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