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 \(A_{i1},\ A_{i2},\ ...,\ A_{im}\).
Output format
Print a single integer denoting the total number of safe paths modulo \(10^9+7\).
Constraints
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
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor