すぬけ君は,"s でt t" というダジャレを思いついたが,忘れてしまった.すぬけ君は以下のことを覚えている.
(s, t) として考えられる組み合わせの個数を 1,000,000,007 で割ったあまりを求めよ.ただし,文字は A 種類存在するものとする.
N M A
条件を満たす文字列の組 (s, t) の個数を 1,000,000,007 で割ったあまりを出力せよ.
3 2 2
14
200 50 1000
678200960