Love Story V

Time Limit: 2000 ms

Memory Limit: 65535 ms

Description

Daiyu Lin and Baoyu Jia are two principal characters of A Dream in Red Mansions. Lin is a well-educated and intelligent young woman who is portrayed in a highly sympathetic light. The romance between Daiyu and Baoyu forms one of the main threads of the book and in many readers' eyes, Lin is the book's leading lady. She hates excessive etiquette, so does Baoyu. Both Lin and Jia are same interest and dream, and they have been honesty to love.
Today, they are playing the chess with a chessboard of N * M in size. They must obey the following rules: At first, some black pieces are put on the chessboard. The player should put the white pieces on the empty cells. Each time one should choose a circuit and put white pieces to occupy it. Be careful one cell doesn’t mean a circuit. At last, the chessboard will be full of pieces and has no empty cells. It’s guaranteed that it doesn’t contain an empty cell which is unreachable. They want to know how many ways to solve it.

Input

Input contains multiple test cases. The first line contains two integers N and M (1 <= N, M <= 10). Each of the next N lines contains M numbers (either 0 or 1) separated by a space. Number 0 means a cell which is placed black piece and number 1 means an empty cell.

Output

For each case just output one line with the number of ways. It’s guaranteed that it does not exceed 2^63 – 1.

Sample Input

6 3
1 1 1
1 0 1
1 1 1
1 1 1
1 0 1
1 1 1

Sample Output

3

Hint

Source

方静远

提交代码