小P家裡養了很多隻蛇，他每天都會陪牠們玩。

怎麼玩呢？ 他把家裡劃分成N*M的方格，接著把這些蛇擺上地板。

每個方格只能被一隻蛇的身體容納，所以每隻蛇的位置都可以用一串連續方格表示。

這些蛇由於很害羞，所以他們都咬著自己的尾巴。也就是每隻蛇都形成一個環狀。

然而有些格子上有插座，如果一隻蛇佔據了有插座的格子，這樣就少一個插座用很不方便。

所以小P希望有插座的格子不能被蛇佔據。

而且小P也不希望沒有插座的格子上面是空的，也就是希望每個格子都被恰好一隻蛇佔據。

小P給了你他家地板的平面圖，他想問你總共有幾種放蛇的方法能符合上述條件。

因為方法數太多了，請輸出MOD 1000000007的結果

值得注意的是擺幾條蛇完全隨意，你可以一條都不擺或擺二三十條。