Problem Statement

315-san is playing a single-player board game.
This board game is played using $V$ vertices, one piece, and a sheet of paper divided into a grid of size $V \times V$.
Numbers are written on the paper, and the number written in the cell at the $i$-th row from the top and the $j$-th column from the left is $E_{i,j}$.
If the piece is placed on vertex $i$ and $E_{i,j}=1$, the piece can be moved to vertex $j$ on the next turn.
315-san must move the piece every turn.
Output Yes if, by moving the piece appropriately, from whichever vertex the piece starts, any vertex of your choice can be selected as the vertex where the piece is located after $D$ turns; otherwise, output No.
If, depending on how the piece is placed and moved, the piece may become unable to move partway through, output No.

Input

$V\ D$
$E_{1,1}\ \cdots\ E_{1,V}$
$\vdots$
$E_{V,1}\ \cdots\ E_{V,V}$

• $1 \leq V \leq 2000$
• $1 \leq D \leq 10^{18}$
• $E_{i,j}$ is $0$ or $1$, and $E_{i,j}=1$ means that the piece can be moved from vertex $i$ to vertex $j$ in one turn
• $E_{i,j}=E_{j,i}$
• All inputs are integers

Output

Output Yes if the condition is satisfied, and No otherwise.
Print a newline at the end.

Sample

3 3
011
101
110

Yes

6 5
000111
000111
000111
111000
111000
111000

No

5 640000
00100
00100
11111
00100
00100

Yes