У Кёи Оотори есть сумка с n цветными мячиками, раскрашенными k различными цветами. Цвета пронумерованы от 1 до k. Мячики одного цвета неотличимы друг от друга. Юноша вынимает мячики из сумки один за другим, пока сумка не опустеет. Он заметил, что для всех i от 1 до k - 1 он вынул последний мяч цвета i до того, как он вынул последний мяч цвета i + 1. Теперь ему интересно, сколько существует различных последовательностей цветов вынутых мячей, удовлетворяющих данному условию.
Выходные данные
Выведите единственное целое число — остаток от деления на 1 000 000 007 количества различных последовательностей цветов мячей, удовлетворяющих условию.
Примечание
В первом примере у нас есть два мяча цвета 1, два мяча цвета 2, и один мяч цвета 3. Три возможных способа таковы:
1 2 1 2 3
1 1 2 2 3
2 1 1 2 3
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2
2
1
|
3
|
|
2
|
4
1
2
3
4
|
1680
|