PIMM 파티

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

수석 인간관계 연구원인 종현의 말에 따르면, PIMM 회원들은 근성과 같은 인싸(I)와, 윤수와 같은 아싸(A)로 분류할 수 있다. 인싸들은 다른 사람과 말하는 것을 좋아하며, 상하좌우로 인접한 각 $1$칸 안에 $1$명 이상의 사람이 있으면 행복해 한다. 아싸들은 다른 사람의 쓸데없는 말을 계속 듣는 것을 싫어하며, 상하좌우로 인접한 $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$로 나눈 나머지를 한 줄에 출력한다.