| Codeforces Round 141 (Div. 2) |
|---|
| Закончено |
Мальчик Вася очень любит рисовать фракталы.
Он делает это следующим образом. Сперва мальчик вырезает из клетчатой бумаги квадрат размером 2 × 2 клеток и закрашивает некоторые из них в черный цвет. Вырезанный квадрат мальчик называет шаблоном фрактала. Затем он берет чистый квадратный лист и рисует фрактал по следующему алгоритму:
- Лист делится на 4 одинаковых квадрата. Часть из них закрашивается в черный цвет в соответствии с шаблоном фрактала.
- Каждый из квадратов, оставшихся белыми, разбивается на 4 меньших белых квадрата, некоторые из них закрашиваются в соответствии с шаблоном фрактала. Каждый из квадратов, оставшихся черными, разбивается на 4 меньших черных квадрата.
На каждом из последующих шагов повторяются действия шага 2. Чтобы нарисовать фрактал, мальчик может выполнить произвольное положительное количество шагов алгоритма, но не менее двух шагов. То есть шаг 2 должен быть выполнен хотя бы 1 раз. Полученная картинка (квадрат с закрашенными клеточками) и будет являться фракталом. На рисунке ниже изображен процесс рисования фрактала (здесь мальчик выполнил 3 шага алгоритма).
Одним вечером Вася очень устал и поэтому, он не стал рисовать фрактал, а просто взял лист бумаги, начертил на нем поле из n × m клеток и некоторые из них закрасил черным цветом.
Теперь ему интересно сколько есть квадратов на поле таких, что существует фрактал, построенный по указанному выше алгоритму, и совпадающий с этим квадратом. Квадрат считается совпадающим с фракталом, если он и фрактал состоят из одинакового количества единичных неделимых клеток и цвет каждой единичной клетки квадрата совпадает с цветом соответствующей клетки фрактала.
В первой строке записаны через пробел два целых числа n, m (2 ≤ n, m ≤ 500) — количество строк и количество столбцов поля соответственно.
В следующих n строках содержатся по m символов — описание поля, нарисованного Васей. Символ «.» обозначает белую клетку, символ «*» — черную.
Гарантируется, что в описании поля не встречается никаких символов кроме «.» и «*».
В единственной строке выведите единственное целое число — количество квадратов на поле, таких, что на этих квадратах нарисован фрактал, который можно получить описанным выше способом.
6 11
......*.***
*.*.*....**
.***....*.*
..***.*....
.*.*.....**
......*.*..
3
4 4
..**
..**
....
....
0
Ответ для первого примера приведен на рисунке. Фракталы обведены красной, синей и зеленой линией.
Ответ для второго примера 0, так как не существует фрактала, совпадающего с данным рисунком.
