No.3053 2.5 色で色塗り

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 7
作問者 : square1001square1001 / テスター : tatyamtatyam
3 ProblemId : 2898 / 出題時の順位表

???「ものの種類数って、なんで $0$ 以上の整数じゃないといけないんだろう?$-1$ や $\pi$ でもいいのに」

yuki2019「???」

???「では、以下の問題を解いてびっと!」

そこで、問題だびっとー!

問題文

正の整数 $N, M$ が与えられます。$N+M$ 頂点のグラフ $G$ は、頂点に $1, 2, 3, \dots, N+M$ の番号がつけられており、番号 $i$ の頂点と $j$ の頂点を結ぶ辺がすべての $(i, j) \ (1 \leq i \leq N, N+1 \leq j \leq N+M)$ に対してある。グラフ理論の用語で言えば、完全二部グラフ $K_{N, M}$ だびっと。

このグラフ $G$ を $2.5$ 彩色する方法は何通りあるんだびっと?

ただし、$2.5$ 彩色とは、グラフの頂点を $2.5$ 種類の色の中からどれか $1$ つで塗ったときに、どの辺についても $2$ つの端点が違う色になっているように色を塗ることだびっと!

実は、答えは有理数 $P \div Q$ ($P, Q$ は整数) の形で表せちゃうんだびっと。$X^{-1}$ を $X$ の $mod \ 1 \ 000 \ 000 \ 007$ での逆元として、$P \times Q^{-1}$ を $1 \ 000 \ 000 \ 007$ で割った余りを出力せよ

入力

入力は以下の形式で与えられるんだびっと。

$N$
$M$

出力

$P \times Q^{-1}$ を $1 \ 000 \ 000 \ 007$ で割った余りを 1 行に出力してびっと!
最後の改行は忘れてびっと=>=>=>=>=>=>=>=>=>=>=>=>=>=>=>=>=>=>=>=>!(エイプリルフール)

制約

すべての入力データは、以下の制約を満たすびっと。

  • $1 \leq N \leq 5k$
  • $1 \leq M \leq 5k$

サンプル

サンプル1
入力
2
2
出力
62500007

$K_{2, 2}$ を $2.5$ 彩色する方法の数は $\frac{105}{16}$ 通りです。

サンプル2
入力
1
3
出力
937500015

$K_{1, 3}$ を $2.5$ 彩色する方法の数は $\frac{135}{16}$ 通りです。

サンプル3
入力
7
7
出力
609214669

$K_{7, 7}$ を $2.5$ 彩色する方法の数は $-\frac{1626932985}{16384}$ 通りです。

場合の数が負の数になってしまう?「???」という人 (?) は一体何だったんでしょうか。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。