A group of people is going for a fun trip to a city coordinated at (1, 1). During their visit, a network started spreading all over the world. After knowing about the network, they decided to safely return to their home town coordinated at (n, m). Among all the paths from (1, 1) to (n, m), some got in the contact with this network. They want to avoid networked paths and hence started calculating the total number of safe paths. Since it can take them a lot of time to find all the safe paths, so they have asked you to help.
You have been given a map in the form of a matrix A of size n×m. Each coordinate represents a city on the map. You are required to find the total number of safe paths starting from city (1, 1) and ending at city (n, m). You are allowed to move either right or down in a single move, that is, if you are at city (x, y), then you can go to either (x+1, y) or (x, y+1) in a single move. You are not allowed to move outside the map.
A path is networked if the product of all the numbers in the path is divisible by X.
Input format
- The first line of input contains two space-separated integers n m.
- Next n lines contain m space-separated integers Ai1, Ai2, ..., Aim.
Output format
Print a single integer denoting the total number of safe paths modulo 109+7.
Constraints
1≤n, m≤103n×m>11≤Aij≤1018X=212072634227239451
There are two paths in this matrix :
(1,1) -> (1,2) -> (2,2) : Product of path is 1 * 212072634227239451 * 1 = 212072634227239451 which is not safe.
(1,1) -> (2,1) -> (2,2) : Product of path is 1 * 1 * 1 = 1 which is safe and can be taken.
Hence total no of safe paths modulo 109 + 7 = 1
