Problem Background

Windy is lost in a directed graph.

Problem Description

The directed graph has $n$ nodes, numbered from $1$ to $n$. Windy starts at node $1$ and must arrive at node $n$ exactly at time $t$.

Given the directed graph, can you tell Windy how many different paths there are?

The answer should be modulo $2009$.

Note: Windy cannot stay at any node, and the time taken to traverse a directed edge is strictly as given.

Input Format

The first line contains two integers, $n$ and $t$.

From the second to the $(n + 1)$-th line, each line contains a string of length $n$. The $j$-th character $c_{i, j}$ in the $(i + 1)$-th line is a digit. If it is $0$, it means there is no edge from node $i$ to node $j$. Otherwise, it represents the length of the edge from node $i$ to node $j$.

Output Format

Output a single integer representing the answer modulo $2009$.

Sample Input and Output

Input Sample #1

2 2
11
00

Output Sample #1

1

Input Sample #2

5 30
12045
07105
47805
12024
12345

Output Sample #2

852

Notes

Sample Input and Output 1 Explanation

The path is $1 \to 1 \to 2$.

Data Size and Constraints

• For $30\%$ of the data, $n \leq 5$ and $t \leq 30$.
• For $100\%$ of the data, $2 \leq n \leq 10$ and $1 \leq t \leq 10^9$.

见题面 Input 部分

见题面 Output 部分