Here is a DP problem on which I have struggled really bad but in vain. Hence, I would really appreciate you guys to help me out.

Problem : You are given a 2-D grid of n*m dimensions. You are requested to print the number of unique paths from top-left corner to the bottom-right corner such that the product of all the values in the path contains odd numbers of divisors. For each cell you can either move to right or down.

Input: n, m Output: Print a single integer denoting number of unique paths from top-left to bottom-right corner such that the product of all values in the path contains odd number of divisors. Print answer modulo 1e9 + 7.

Constraints: 1 <= n, m <= 100 value[i, j] <= 30

Example: Input: n = 3, m = 2

grid:  1 1
           3 1
           3 1 

      Output: 2

Explanation: Here are 2 unique paths: 1-> 3-> 3-> 1, Product = 9, Number of divisors of 9 are 1, 3, 9 which is odd. 1-> 1-> 1-> 1, Product = 1, Number of divisors of 1 is only 1 only, which is odd.