Дана квадратная таблица \(n \times n\) и целое число \(k\). Поставьте в каждую клетку по одному целому числу так, чтобы все условия были удовлетворены.
- Все числа в таблице должны быть от \(1\) до \(k\) включительно.
- Минимальное число \(i\)-й строки должно быть равно \(1\) (\(1 \le i \le n\)).
- Минимальное число \(j\)-го столбца должно быть равно \(1\) (\(1 \le j \le n\)).
Найдите количество способов расставить числа в клетках. Так как ответ может быть очень большой, найдите его по модулю \((10^{9} + 7)\).
Пример правильной (слева) и неправильной (справа) таблицы, где \(n=k=2\). Выходные данные
Выведите ответ по модулю \((10^{9} + 7)\).
Примечание
В первом примере есть \(7\) способов.
Во втором примере убедитесь, что вы выводите ответ по модулю \((10^{9} + 7)\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 2
|
7
|
|
2
|
123 456789
|
689974806
|