битмаски

Для поиска полезных ископаемых ученые разработали специальный сканер.

Представим область для поисков как таблицу из \(k\) строк и \(n\) столбцов. Нумерация строк идет от \(1\) до \(k\) сверху вниз, нумерация столбцов от \(1\) до \(n\) слева направо. В каждой клетке таблицы могут находиться полезные ископаемые.

Сканер работает следующим образом: он может быть запущен в столбце \(p\) и возвращает количество клеток в зоне сканирования, которые содержат полезные ископаемые. Зона сканирования включает все клетки столбца \(p\), верхние \(k-1\) клетку столбца \(p-1\), верхние \(k-2\) клетки столбца \(p-2\), и так далее. На рисунке показана зона сканирования для поля с \(k = 3\), \(n=5\) и всех значений \(p\).

Вам даны значения, которые вернул сканер для всех \(p\), обозначим за \(b_p\) значение в столбце \(p\). Будем называть таблицу, где для каждой клетки определено, находятся ли в ней полезные ископаемые, корректной, если для нее сканер возвращает верные значения. Например, если в примере выше сканер вернул значения \([2, 1, 2, 3, 2]\), то одна из корректных таблиц может выглядеть следующим образом (клетки, содержащие ископаемые, обозначены черным треугольником):

По заданным значениям, которые вернул сканер, определите количество корректных таблиц и выведите остаток от деления этого количества на число \(10^9+7\). Обратите внимание, что, возможно, сканер неисправен, и корректных таблиц вообще нет, тогда необходимо вывести \(0\).

Формат входных данных
В первой строке даны два числа \(n\), \(k\) — количество столбцов и строк, соответственно (\(1 \le n \le 200\), \(1 \le k \le 7\)).

Во второй строке даны \(n\) чисел \(b_1, b_2, \ldots, b_n\) — значения, которые вернул сканер (\(0 \le b_i \le k^2\)).

Формат выходных данных
Выведите единственное число — остаток от деления количества различных корректных таблиц на \(10^9 + 7\).

Федот — дизайнер, ему поручена ответственная работа по художественной укладке плитки черного и белого цвета. Его последнее задание — уложить черные и белые плитки в квадрате n × n.

Федот любит свою работу и всегда тщательно готовится к каждому проекту. Федот считает, что два квадрата похожи, если один из них можно получить из другого несколько раз заменив цвета в какой-то строке или столбце на противоположные. Федот заметил, что клиенты никогда не смотрят на всю работу целиком, обычно поле их зрения ограничивается квадратом k × k. Для оценки эскизов он ввел специальную величину — сложность. Она равна числу пар не похожих друг на друга квадратов k × k, которые встречаются в картине.

Методом проб и ошибок Федот установил, что клиентам нравятся картины определенной сложности. Слишком большая сложность похожа на хаос, а слишком малая навевает скуку, считает Федот.

Прежде чем класть плитку, Федот подготовил несколько эскизов. Помогите Федоту вычислить их сложность.

Входные данные
Первая строка входного файла содержит два целых числа n и k (1 ≤ k ≤ n ≤ 500). Следуюшие n строк содержат описание эскиза. Каждая из них имеет длину n и состоит из символов b и w, которые соответствуют белому и черному цветам плиток.

Выходные данные
В первой строке выходного файла выведите одно целое число q — сложность картины.

Примеры

№	Входные данные	Выходные данные
1	2 1 bw wb	0
2	3 2 bwb wbb bbw	3