Однажды маленький Вася нашел записную книжку мамы. В ней были записаны n имен ее друзей, каждое из которых необыкновенным образом было длиной ровно m букв. Пронумеруем имена от 1 до n в том порядке, в котором они записаны.
Так как мамы не было дома, Вася решил поиграть с именами: он выбирал три целых числа i, j, k (1 ≤ i < j ≤ n, 1 ≤ k ≤ m), и менял местами у имен с номерами i и j префиксы длиной ровно k символов. Например, если у имен «CBDAD» и «AABRD» поменять местами префиксы длиной 3, то получатся имена «AABAD» и «CBDRD».
Вам интересно, сколько возможных различных имен могло быть записано на месте имени номер 1, если Васе разрешено делать любое количество описанных действий. Делая каждое действие, Вася выбирает числа i, j, k независимо от предыдущих ходов и исключительно по своему усмотрению. Искомое число может быть очень большим, поэтому необходимо найти только остаток от деления этого числа на 1000000007 (109 + 7).