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.
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.
- 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.
- 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])
1 3 2 1 1 3 1 3 1
There are 2 Beautiful Paths * A -> A -> A -> A * A -> A -> A -> A