Thạch đang ở một trò chơi đặc biệt trong khu vui chơi. Đó là một mê cung có dạng bảng hình chữ nhật, có kích thước \(m \times n\) (\(m\) dòng, \(n\) cột). Trong này có \(k\) ô chứa vật cản. Ô nằm ở hàng \(i\), cột \(j\) được kí hiệu là ô \((i, j)\).

Vào thời điểm ban đầu, Thạch đứng ở ô \((1, 1)\). Tại mỗi lượt, cậu chỉ được đi xuống dưới hoặc sang phải. Dĩ nhiên, Thạch không được phép đi vào ô có vật cản. Mục tiêu của trò chơi là đi tới ô đích ở \((m, n)\).

Tuy nhiên, điểm đặc biệt ở mê cung này là: Mọi vật cản đều di chuyển theo mỗi bước chân của Thạch (có lẽ là do sân này có gắn cảm biến và nhiều cỗ máy đặc biệt chăng?). Quy luật như sau:

• Sau khi đi xuống dưới một hàng thì mọi vật cản dịch lên trên \(1\) đơn vị, riêng những vật cản ở dòng \(1\) bây giờ sẽ được đẩy "lên" dòng cuối \(m\)
• Nếu đi qua phải thì mọi vật cản dịch sang trái \(1\) đơn vị, riêng những vật nằm trên cột \(1\) sẽ được đẩy sang cột cuối \(n\).
• Nói cách khác, các vật cản dịch chuyển theo vòng tròn.
• Sau một bước đi bất kì của Thạch, nếu có vật cản nào đó dịch tới chỗ cậu đang đứng thì Thạch sẽ bị loại khỏi mê cung và coi như thua cuộc (kể cả sau khi bước tới ô đích).

Việc giành chiến thắng có vẻ quá đơn giản với một gamer như Thạch. Vì thế điều cậu ấy đang quan tâm hơn hết là: Đếm số cách khác nhau để cậu có thể đi tới được đích đến tại vị trí \((m, n)\), chia lấy dư cho \(2004010501\).

Bạn hãy lập trình giải quyết bài toán trên.

Input

• Dòng đầu tiên chứa ba số \(m, n, k\) \((0 \leq k \leq m \times n, 1 \leq m, n \leq 1000)\)
• \(m\) dòng tiếp theo, mỗi dòng chứa một xâu kí tự độ dài \(n\). Nếu kí tự thứ \(j\) trên dòng thứ \(i\) là #, ô \((i, j)\) là ô chứa vật cản. Ngược lại, nếu là . thì ô \((i, j)\) là ô trống.
• Dữ liệu đảm bảo có đúng \(k\) ô # trong mê cung, và ô \((1, 1)\) lúc đầu không chứa vật cản.

Output

• In ra một dòng duy nhất là kết quả bài toán

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(m + n \leq 20\)
• Subtask \(2\) (\(25\%\) số điểm): \(k = 0\)
• Subtask \(3\) (\(15\%\) số điểm): \(n = 2\)
• Subtask \(4\) (\(35\%\) số điểm): không có ràng buộc gì thêm

Example

2 3 1
...
..#

2