CF704C Black Widow

Natalia Romanova is trying to test something on the new gun S.H.I.E.L.D gave her. In order to determine the result of the test, she needs to find the number of answers to a certain equation. The equation is of form:  Where  represents logical OR and  represents logical exclusive OR (XOR), and $ v_{i,j} $ are some boolean variables or their negations. Natalia calls the left side of the equation a XNF formula. Each statement in brackets is called a clause, and $ v_{i,j} $ are called literals. In the equation Natalia has, the left side is actually a 2-XNF-2 containing variables $ x_{1},x_{2},...,x_{m} $ and their negations. An XNF formula is 2-XNF-2 if: 1. For each $ 1

The first line of input contains two integers $ n $ and $ m $ ( $ 1

Print the answer modulo $ 1000000007 $ ( $ 10^{9}+7 $ ) in one line.

The equation in the first sample is: The equation in the second sample is: The equation in the third sample is: