Placement of Rooks

You need to determine the number of ways to position N rooks on an N×N chessboard such that no two rooks share the same row or column. Additionally, certain cells on the board are restricted and cannot have rooks placed on them.

Input

The first line contains the integer N (1 ≤ N ≤ 3000). The next N lines each contain N characters, representing the board's cells. A character '1' indicates that a rook can be placed in that cell, while '0' indicates that it cannot.

Output

Since the result can be very large, output a single number — the remainder of the total number of valid arrangements divided by 2.

Examples