1474: Ферзі


Submit solution


Points:30
Time limit:1.0s
Python 32.0s
java82.0s
Memory limit:500M
Python 3500M
java8500M
Author:

Problem type

Марта ще у сиву давнину, у першому класi, вигравала чемпiонат областi по шахах. Тепер вона уже студентка i хоче вiдновити втраченi навички цiєї гри. Оскiльки її математичнi горизонти значно розширилися, то вона iнколи придумує рiзнi шаховi задачi. Ось одна iз них. На нестандартнiй шаховiй дошцi розмiрнiстю N х M розмiщенi деякi фiгури. Скiлькома способами на цiй дошцi можна розмiстити одного чи бiльше ферзiв так, щоб нiякi з них не загрожували один одному. Ферзя не можна поставити на уже зайняту клiтину. Вiдомо, що ферзь б’є горизонтально, вертикально та по дiагоналi. Ферзi не можуть загрожувати один одному, якщо мiж ними є iнша фiгура.

Формат вхідних даних

Перший рядок мiстить цiлi числа N i M. Наступнi N рядкiв мiстять M символiв, кожен з яких описує шахову дошку: ’#’ вказує на зайняту клiтину, а ’.’ - на вiльну клiтину.

Обмеження:

1 <= N <= 50

1 <= M <= 5

Формат вихідних даних

Для кожного тесту в окремому рядку виведiть вiдповiдь на поставлене завдання. Оскiльки вiд- повiдi можуть бути достатньо великими числами, то виведiть їх по модулю 1000000007.

Приклад вхідних даних

2 2
# .
. .

Приклад вихідних даних

3

Comments

There are no comments at the moment.