You have matrix $*a*$ of size $*n* × *n*$. Let's number the rows of the matrix from $1$ to $*n*$ from top to bottom, let's number the columns from $1$ to $*n*$ from left to right. Let's use $*a*_{*ij*}$ to represent the element on the intersection of the $*i*$-th row and the $*j*$-th column.

Matrix $*a*$ meets the following two conditions:

• for any numbers $*i*, *j*$ ($1 ≤ *i*, *j* ≤ *n*$) the following inequality holds: $*a*_{*ij*} ≥ 0$;
• .

Matrix $*b*$ is strictly positive, if for any numbers $*i*, *j*$ ($1 ≤ *i*, *j* ≤ *n*$) the inequality $*b*_{*ij*} > 0$ holds. You task is to determine if there is such integer $*k* ≥ 1$, that matrix $*a*^{*k*}$ is strictly positive.

Input

The first line contains integer $*n*$ ($2 ≤ *n* ≤ 2000$) — the number of rows and columns in matrix $*a*$.

The next $*n*$ lines contain the description of the rows of matrix $*a*$. The $*i*$-th line contains $*n*$ non-negative integers $*a*_{*i*1}, *a*_{*i*2}, ..., *a*_{*in*}$ ($0 ≤ *a*_{*ij*} ≤ 50$). It is guaranteed that .

Output

If there is a positive integer $*k* ≥ 1$, such that matrix $*a*^{*k*}$ is strictly positive, print "YES" (without the quotes). Otherwise, print "NO" (without the quotes).