괴도 강산

오늘 밤, 다녀가겠담.

괴도 강산

예고장을 받은 박물관 관장 택희는 패닉에 빠졌다. 강산은 세계 최악의 괴도이고, 예고장이 도착한 곳에는 보물이 하나도 남지 않는다. 그래도 택희는 포기하지 않았다. 사비를 털어 최신 위치추적기를 잔뜩 사들였고, 이것으로 강산을 붙잡으려 한다.

택희의 박물관은 $N$행 $M$열 격자다. $i$행 $j$열 칸을 $(i, j)$라고 부른다. 박물관 곳곳에는 보석이 놓여 있고, 택희는 보석이 없는 칸 중 일부에 위치추적기를 설치했다. 강산이 위치추적기를 그대로 들고 나가면, 강산은 오랜 괴도 생활 끝에 결국 경찰에 붙잡히고 만다.

강산은 택희가 위치추적기를 여럿 설치했다는 사실을 이미 알아냈다. 박물관에 있는 보석을 모두 훔치려고 강산이 쓰려는 전략은 다음과 같다.

• 행 또는 열 하나를 고른다. 고른 행은 왼쪽 칸부터 오른쪽 칸까지, 고른 열은 위쪽 칸부터 아래쪽 칸까지 빠짐없이 지나가면서 다음 두 작업을 처리한다.
  • 보석이나 위치추적기가 놓인 칸을 지나가면 그 보석이나 위치추적기를 반드시 가져온다.
  • 원래 위치추적기가 있었지만 지금은 비어 있는 칸을 지나가고 있고 손에 든 위치추적기가 하나라도 있다면, 그 칸에 반드시 하나를 내려놓는다.
• 보석을 모두 손에 넣었고 손에 든 위치추적기가 0개라면 박물관을 떠난다. 그렇지 않다면 다시 행 또는 열 하나를 골라 위 작업을 반복한다.

택희도 만만치 않다. 강산의 전략을 간파한 택희는 위치추적기가 아닌 보석은 어느 것이든 도난당할 경우 즉시 그 위치에 경비원이 출동할 수 있도록 준비해 두었다. 그래서 다음 제약이 붙는다.

• 강산이 위치추적기가 아닌 보석을 하나 훔치면, 그 칸이 속한 행과 열에는 다시 들어가지 못한다.

예를 하나 보자.

위 그림에서 박물관은 4행 5열 격자이고, 보석은 $(1, 5)$, $(3, 4)$, $(4, 3)$에, 위치추적기는 $(1, 1)$, $(2, 2)$, $(2, 5)$, $(4, 4)$에 놓여 있다. 이 상황에서 강산은 다음 순서로 보석을 모두 훔칠 수 있다.

1. 4행을 지나가면서 $(4, 3)$의 보석과 $(4, 4)$의 위치추적기를 가져온다.
2. 4열을 지나가면서 $(3, 4)$의 보석을 가져오고, $(4, 4)$에 위치추적기를 다시 내려놓는다.
3. 1행을 지나가면서 $(1, 1)$의 위치추적기와 $(1, 5)$의 보석을 가져온다.
4. 1열로 들어가 $(1, 1)$에 위치추적기를 다시 내려놓는다. 이때 강산은 $(1, 1)$, $(2, 1)$, $(3, 1)$, $(4, 1)$을 모두 지나가야 한다. $(1, 1)$만 들르고 곧바로 빠져나오는 것은 불가능하다.

$(2, 2)$와 $(2, 5)$의 위치추적기는 처음부터 건드리지 않았으므로 문제가 되지 않는다. 4번 과정에서 1열 대신 1행으로 들어가는 것은 불가능하다. $(1, 5)$의 보석을 이미 훔쳐서 1행에는 경비원이 서 있기 때문이다.

강산에게 타협은 없다. 박물관에 놓인 보석을 하나도 빠짐없이 가져오면서, 위치추적기 때문에 경찰에 쫓기는 일도 피해야 한다.

강산이 오늘도 목적을 이룰 수 있을지 판정하자.

첫째 줄에 박물관의 행의 수 $N$과 열의 수 $M$이 주어진다. ($1 \le N, M \le 10^3$)

이어 $N$개의 줄에 걸쳐 박물관의 각 행의 모습이 $M$개의 문자로 주어진다. 각 문자는 ., *, # 중 하나다. .은 아무것도 놓여 있지 않은 빈 칸, *는 보석이 놓인 칸, #은 위치추적기가 놓인 칸을 뜻한다.

박물관에는 보석이 적어도 하나 있다.

강산이 목적을 이룰 수 있다면 첫째 줄에 1을, 그렇지 않다면 0을 출력한다.