PIMM 파티

PIMM 회장 민규는 여름방학을 맞아 파티를 열기로 했다. 회장 역할에 진심인 민규는 모두가 행복한 파티를 만들고자 한다.

수석 인간관계 연구원 종현에 따르면 PIMM 회원은 근성이처럼 인싸(I)와 윤수처럼 아싸(A)로 나눌 수 있다. 인싸는 다른 사람과 말하는 것을 좋아해서, 상하좌우로 인접한 칸 안에 1명 이상의 사람이 있으면 행복해한다. 아싸는 다른 사람의 쓸데없는 말을 계속 듣는 것을 싫어해서, 상하좌우로 인접한 칸 안에 인싸가 없으면 행복해한다.

민규는 $N \times M$ 직사각형 모양의 파티룸을 빌렸다. 정환에게서 인싸 $X$명과 아싸 $Y$명이 파티에 참여한다는 연락을 받았다.

영도는 민규를 대신해 파티룸에 자리를 배정한다. 아싸가 먼저 배치된 파티룸 정보가 주어졌을 때, 모두가 행복한 파티가 되도록 자리를 배치하는 경우의 수를 구하라.

첫 줄에 $N$, $M$, $X$, $Y$가 공백으로 구분되어 한 줄에 주어진다. ($1 \le N,M \le 7;$ $1 \le X, Y \le N \times M;$ $X+Y \le N \times M$)

다음 $N$개의 줄에는 아싸가 배치된 파티룸 정보가 길이 $M$의 문자열로 주어진다. *는 빈칸이고, A는 아싸가 있는 위치이다.

파티룸에서 인싸를 배치할 $X$개의 칸을 순서에 상관없이 선택할 때, 모두가 행복한 파티가 되는 경우의 수의 합을 $1\,000\,000\,007$로 나눈 나머지를 한 줄에 출력한다.