推箱子是一款經(jīng)典電子游戲，愛麗絲很喜歡玩，但是她有點玩膩了，現(xiàn)在她想設(shè)計一款拉箱子游戲。

拉箱子游戲需要玩家在一個 N × M 的網(wǎng)格地圖中，控制小人上下左右移動，將箱子拉到終點以獲得勝利。

現(xiàn)在愛麗絲想知道，在給定地形（即所有墻的位置）的情況下，有多少種不同的可解的初始局面。

【初始局面】 的定義如下：

1、初始局面由排列成 N × M 矩形網(wǎng)格狀的各種元素組成，每個網(wǎng)格中有且只有一種元素?？赡艿脑赜校嚎盏亍?、小人、箱子、終點。

2、初始局面中有且只有一個小人。

3、初始局面中有且只有一個箱子。

4、初始局面中有且只有一個終點。

【可解】 的定義如下：

通過有限次數(shù)的移動小人（可以在移動的同時拉箱子），箱子能夠到達終點所在的網(wǎng)格。 

【移動】 的定義如下：

在一次移動中，小人可以移動到相鄰（上、下、左、右四種選項）的一個網(wǎng)格中，前提是滿足以下條件：

1、小人永遠不能移動到 N × M 的網(wǎng)格外部。

2、小人永遠不能移動到墻上或是箱子上。

3、小人可以移動到空地或是終點上。

【拉箱子】 的定義如下：

在一次合法移動的同時，如果小人初始所在網(wǎng)格沿小人移動方向的反方向上的相鄰網(wǎng)格上恰好是箱子，小人可以拉動箱子一起移動，讓箱子移動到小人初始所在網(wǎng)格。

即使?jié)M足條件，小人也可以只移動而不拉箱子。

第一行兩個正整數(shù) N 和 M，表示網(wǎng)格的大小。

接下來 N 行，每行 M 個由空格隔開的整數(shù) 0 或 1 描述給定的地形。其中 1 表示墻，0 表示未知的元素，未知元素可能是小人或箱子或空地或終點，但不能是墻。 

2 4
0 0 0 0
1 1 1 0

13

13 種可解的初始局面示意圖如下：

人終箱空

墻墻墻空

********

人終空箱

墻墻墻空

********

人空終箱

墻墻墻空

********

箱人終空

墻墻墻空

********

空人終箱

墻墻墻空

********

箱終人空

墻墻墻空

********

空終人箱

墻墻墻空

********

箱終空人

墻墻墻空

********

箱空終人

墻墻墻空

********

空箱終人

墻墻墻空

********

箱終空空

墻墻墻人

********

箱空終空

墻墻墻人

********

空箱終空

墻墻墻人

對于 30% 的數(shù)據(jù)，N, M ≤ 3.

對于 100% 的數(shù)據(jù)，0 < N, M ≤ 10.