Labyrinth

Time Limit: 1 Second    Memory Limit: 32768 KB

The labyrinth map represents a checkquered square N*N, with some checks prohibited for passing. A step in the labyrinth consists of moving from one non-prohibited check to another non-prohibited check, which has a common side with the given check. A path is some sequence of steps. It is required to move from check (1, 1) to check (N, N) in exactly K steps, that is, after K-th step appear in check (N, N). Find the amount of different ways to do it.

Note: Any check, including the starting and the ending ones, may be passed several times. The starting and the ending checks are always non-prohibited.

1 < N <= 20
0 < K <= 50

Input

The first line of the input file contains two numbers: N and K, separated by one or more spaces. The following N lines with N symbols in each contain the map of the labyrinth beginning with check (1,1). Symbol '0' marks non-prohibited checks and symbol '1' marks prohibited ones.

Process to the end of file.

Output

The output file must contain the result - the amount of possible paths of length K.

Sample Input

3 6
000
101
100
3 6
000
111
000

Sample Output

5
0

Submit