問題一覧 > 通常問題

No.1762 🐙🐄🌲

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

問題文

多項式が大好きな Nyaan さんは「タコ」と「うし」を組み合わせて多項式を作ることにしました。

次の条件を満たす木を $N$ 頂点のタコうし木と呼びます。

  • 頂点にはそれぞれ $1$ から $N$ までの番号が振られていて、各頂点には「タコ」か「うし」のいずれかの絵が書かれている。
  • 「タコ」の絵が描かれた頂点の次数は $\mathbf{8}$ 以下である。
  • 「うし」の絵が描かれた頂点の次数は $\mathbf{4}$ である。
  • 同じ絵が描かれた頂点は隣接しない。

また、タコうし木の頂点のうち、「タコ」の絵が描かれた次数が $8$ である頂点のことを "完全なタコ" と呼びます。

$N, P$ が与えられます。完全なタコをちょうど $P$ 個持つ $N$ 頂点のタコうし木の個数を $998244353$ で割ったあまりを求めてください。

制約

  • 入力は全て整数である。
  • $2 \leq N \leq 5 \times 10^5$
  • $0 \leq P \leq N$

入力

$N\ P$

出力

答えを $1$ 行に出力してください。

サンプル

サンプル1
入力
5 0
出力
5

頂点数 $5$ で完全なタコが存在しない頂点ラベルなしタコうし木の形は次の $1$ 通りのみで、ラベルのつけ方は $5$ 通りあります。

サンプル2
入力
13 0
出力
48048000

頂点数 $13$ で完全なタコが存在しない頂点ラベルなしタコうし木の形は次の $2$ 通りです。
頂点ラベルのつけ方はそれぞれ $\frac{13!}{144}$ 通り、 $\frac{13!}{1296}$ 通りで、合計 $\frac{13! \cdot 10}{1296} = 48048000$ 通りになります。

サンプル3
入力
133333 1333
出力
425602496

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