Prof. Bari loves to play with string. He is also very skilled in drawing. One day he was drawing a grid. Suddenly, he comes up with an idea. If a string S is given, in how many ways can he put the string in the grid?
As he is a great researcher and of course a problem solver, he could solve it easily. But to make things harder, he changed the grid by putting some ‘#’ in it. Then he asks his students to solve this problem.
In this problem, you are given an N*M grid and a string S. You have to find out in how many distinct ways you can put the string S in the grid. You cannot put any character in the grid where ‘#’ is in. You can only put the characters of the string where ‘.’ is in.
There can have ‘.’ in the grid even after putting the string.
All the characters of the input string may not be distinct.
Input
The first line will contain N and M, the size of the grid (1 ≤ N,M ≤ 50).
The next N lines will have M characters each, denoting the board. The characters will either be a '.' or a '#'.
The next line will be a string S, which will have at most 2500 characters in it. All the letters of the string will be lowercase letters from the English alphabet.
Output
For each case, print the answer modulo 1000000007.
Sample
| Input | Output |
|---|---|
3 3 .#. ### .## abc | 6 |
