No.2529 Treasure Hunter
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 94
作問者 : PCTprobability / テスター : NyaanNyaan
タグ : / 解いたユーザー数 94
作問者 : PCTprobability / テスター : NyaanNyaan
問題文最終更新日: 2023-11-03 22:15:19
問題文
PCT 君は のグリッドで構築される世界の創造神になりました。
以下、上から 番目、左から 番目のマスを と呼ぶことにします。
この世界に、以下の条件を全て満たすようにいくつかのマスを選び秘宝を埋めることにしました。
- 各マスには秘宝は高々 個までしか埋められない。
- 各行の内秘宝は高々 個までしか埋められない。
- 秘宝が埋められているマスは隣り合ってはならない。ただし、この世界では と は隣り合っているものとする。
条件を満たす秘宝の埋め方を で割ったあまりを求めてください。
テストケースは 個与えられるので、それぞれについて答えを求めてください。
制約
- 入力は全て整数である。
- テストケースの の総和は 以下である。
- テストケースの の総和は 以下である。
入力
入力は以下の形式で与えられます。
各ケースは次の形で与えられます。
出力
行出力して最後に改行してください。
行目には 番目のテストケースに対する答えを出力してください。
サンプル
サンプル1
入力
5 4 2 5 6 123 456 1234 5678 3141 5926
出力
35 276561 532350908 204920481 830272369
始めのテストケースに対しては、例えば以下の図 のような配置が条件を満たします。図 は と は両方秘宝が置かれていますが隣り合っているため不適切です。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。