Rar the Cat is playing a video game. The objective of it is to move from one corner of a square room to the opposite corner. However, there are pillars which he cannot go through (obviously) and bombs which will cause him to lose some lives. He will have ~N~ lives at the start. He must reach the opposite corner with at least 1 life. Rar the Cat wonders how many ways can he do it.

Input Specification

Line 1 of input will be ~N~, the number of lives you will have at the start.

Line 2 of input will be the length of the room, ~L~.

The next ~L~ lines of input will be the map of the room. Each line contains ~L~ characters. Every character will be ., P, or a number representing the number of lives you will lose if you go into it. A P represents a pillar. The top left character will not be a pillar.

Output Specification

The number of ways (mod ~1\,000\,003~) he can move from the top left corner of the map to the bottom right corner of the map, without losing all lives, assuming that he only moves down and right.

Constraints

Subtask 1 [100%]

~1 \le N, L \le 100~

Subtask 2 [0%]

Sample test cases.

Sample Input

3
3
.P2
..2
12.

Sample Output

2