Предположим, вы ходите каждый день на занятия. Каждый раз вы приходите в последний момент, и некоторые места в классе уже заняты. Например, сегодня вы с друзьями пришли в класс и обнаружили, что некоторые места уже заняты.
В класс \(n\) рядов по \(m\) мест в каждом ряду. Таким образом, класс можно представить как матрицу \(n \times m\). Символ «.» означает свободное место, а символ «*» означает занятое место. Вам необходимо найти \(k\) соседних свободных мест в одном ряду или в одном столбце. Посчитайте количество способов выбрать места. Два способа считаются различными, если различны множества мест, которые вы выберете.
Выходные данные
Выведите одно число — число способов выбрать \(k\) свободных мест в одном ряду или столбце.
Примечание
В первом примере есть три способа выбрать места. Они перечислены ниже.
- \((1,3)\), \((2,3)\)
- \((2,2)\), \((2,3)\)
- \((2,1)\), \((2,2)\)
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 3 2
**.
...
|
3
|
|
2
|
1 2 2
..
|
1
|
|
3
|
3 3 4
.*.
*.*
.*.
|
0
|