Страх#9011
Усі чогось бояться. Хтось боїться темряви, хтось боїться висоти, хтось боїться Вінні Джонса (всі ми боїмося Вінні Джонса), хтось боїться співати перед їжею.
Страху багато, але найбільший з усіх для Мірка – це вибір землі для посадки полуниці. Земля Мірко може бути описана як матриця з рядками та стовпцями. Частина полів у матриці підходять для посадки полуниці, а частина ні – там ростуть бур'яни. Мірко шукає прямокутні ділянки землі, повністю заповнені полями, придатними для посадки полуниці. Такі прямокутники називаються відповідними прямокутниками. Також Мірко цікавить потенційне значення всіх полів у матриці. Потенційне значення кожного поля в матриці визначається як кількість відповідних прямокутників, що містять це поле.
Оскільки у Мірко проблеми зі своїми страхами, він просить Вас обчислити лише суму потенційних значень усіх полів.
Перший рядок містить два цілі позитивні числа і (1 ≤ n, m ≤ 2000) - розміри ділянки.
Наступні рядків містять символів, що позначають ландшафт. Кожен символ може бути або . (точка), що позначає поле, що підходить для посадки, або #, що позначає бур'яни.
Виведіть суму всіх можливих значень полів матриці.
Приклад 1
Приклад 2
Приклад 3
Наступна матриця визначає потенційну цінність полів ґрунту. Сума всіх потенційних значень дорівнює .
