connected path in a matrix


The problem statement is :
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 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 the city (1,1) and ending at the city (n,m). You are allowed to move either right or down in a single move, that is, if you are at the 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

Note: Since the input matrix can be very large, therefore you are given only K coordinate’s values and remaining coordinates have values W.

The first line contains four space-separated integers n,m,k,w . The next k lines contain three space-separated integers x,y,v denoting the coordinate (x,y) has value v.

Output format

Print a single integer denoting the total number of safe paths modulo 10^9 +7.

my approach toward code:

  #include <iostream>   #include <string>  #include <limits>   #include <algorithm>   using namespace std;   // M x N matrix  #define M 5  #define N 5   // Naive recursive function to find the minimum cost to reach  // cell (m, n) from cell (0, 0) int findMinCost(int cost[M][N], int m, int n)  {   // base case   if (n == 0 || m == 0)     return INT_MAX;  // if we're at first cell (0, 0) if (m == 1 && n == 1)     return cost[0][0];  // include cost of the current cell in path and recur to find minimum // of the path from adjacent left cell and adjacent top cell. return min (findMinCost(cost, m - 1, n), findMinCost(cost, m, n - 1))             + cost[m - 1][n - 1];  }  // main function int main() { int cost[M][N] = {     { 4, 7, 8, 6, 4 },     { 6, 7, 3, 9, 2 },     { 3, 8, 1, 2, 4 },     { 7, 1, 7, 3, 7 },     { 2, 9, 8, 9, 3 } };  cout << "The minimum cost is " << findMinCost(cost, M, N);  return 0; } 

I am getting trouble on how to product the coordinate”s value after every move with having to give a proper matrix of size n*m. Somone please help me .