C. Записная книжка
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

Однажды маленький Вася нашел записную книжку мамы. В ней были записаны 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).

Входные данные

В первой строке входных данных записаны два целых числа n и m (1 ≤ n, m ≤ 100) — количество имен и длина каждого имени соответственно. Далее в n строках расположены имена, каждое состоит ровно из m заглавных латинских букв.

Выходные данные

Выведите единственное целое число — остаток от деления на 1000000007 (109 + 7) количества различных имен, которые могли бы получиться на месте номер 1 после применений описанных действий.

Примеры
Входные данные
2 3
AAB
BAA
Выходные данные
4
Входные данные
4 5
ABABA
BCGDG
AAAAA
YABSA
Выходные данные
216
Примечание

В первом примере Вася на месте имени номер 1 может получить следующие: «AAB», «AAA», «BAA» и «BAB».