Problem Statement:

Given two Integers M,N and a Grid of size M x N, the task is to find number of Beautiful Paths from Top Left Cell (0,0) to Bottom Right Cell(M-1,N-1). A Beautiful Path has the following Constraints:

- From each cell you can either move right or down
- The Product of values along the path should have odd number of factors

Since the Output could be very large, compute it modulo 10^9+7.

Input Format:

First line contains T denoting the Number of Test Cases. Description of T Test cases follows.

- First line of each Test Case contains two integers M,N
- M lines follow, each line containing N integers.

Output Format:

- For each test case, output on a single line, an Integer denoting the Number of Beautiful Paths from top left to bottom right cell modulo 10^9+7.

Constraints:

- 1 \le T \le 10
- 1 \le M,N \le 10^2
- 1 \le A[i][j] \le 30\ \forall\ (i\isin[1,M], j\isin[1,N])

Sample Input:

```
1
3 2
1 1
3 1
3 1
```

Sample Output:

```
2
```

Explanation:

```
There are 2 Beautiful Paths
* A[0][0] -> A[0][1] -> A[1][1] -> A[2][1]
* A[0][0] -> A[1][0] -> A[2][0] -> A[2][1]
```

Please help @galencolin, @ssrivastava990

Not only the above people, anyone can help