Вам дан массив \(a\) из \(n\) целых чисел, в котором все элементы \(a_i\) лежат в диапазоне \([1, k]\). Сколько различных массивов \(b\) из \(m\) целых чисел, где все элементы \(b_i\) лежат в диапазоне \([1, k]\), содержат \(a\) в качестве подпоследовательности? Два массива считаются различными, если они отличаются хотя бы в одной позиции.
Последовательность \(x\) является подпоследовательностью последовательности \(y\), если \(x\) может быть получена из \(y\) путем удаления нескольких (возможно, нуля или всех) элементов.
Поскольку ответ может быть очень большим, выведите его по модулю \(10^9 + 7\).
Примечание
В первом примере, поскольку \(k=1\), существует только один массив размера \(m\), состоящий из целых чисел \([1, k]\). Этот массив (\([1, 1, \ldots, 1]\)) содержит исходный массив в качестве подпоследовательности, поэтому ответ - 1.
Во втором примере есть \(9\) массивов: \([1, 1, 2, 2]\), \([1, 2, 1, 2]\), \([1, 2, 2, 1]\), \([1, 2, 2, 2]\), \([1, 2, 2, 3]\), \([1, 2, 3, 2]\), \([1, 3, 2, 2]\), \([2, 1, 2, 2]\), \([3, 1, 2, 2]\).
В четвертом примере, поскольку \(m=n\), единственным массивом размера \(m\), который содержит \(a\) в качестве подпоследовательности, является сам \(a\).