该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

称一个矩阵在模 $p$ 意义下是神奇的，当且仅当它满足下面两个条件：

• 该矩阵是一个只含 $0$ 到 $p - 1$ 的整数的方阵；
• 矩阵每行，每列的和在模 $p$ 意义下相等。

给定的 $n,p,k$，请你求出模 $p$ 意义下 $n$ 阶神奇的矩阵中每行每列的和均等于 $k$ 的不同矩阵的个数，两个矩阵不同当且仅当它们在至少某一位上的元素不同。

由于答案较大，请你求出答案对 $10^9 +7$（一个质数）取模后的结果。

输入

一行三个整数 $n,p,k$，意义见题目描述。

保证 $1\le n,p\le 10^9, ~0\le k< p$。

输出

一行一个整数，表示模 $p$ 意义下 $n$ 阶神奇的矩阵中每行每列的和均等于 $k$ 的不同矩阵个数对 $10^9 + 7$ 取模后的结果。

2 5 0

5

3 3 2

81