1390: Labyrinth

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 <= 100

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.

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

3 6
000
101
100
3 6
000
111
000

5
0