This problem can be solved with dynamic programming. The easiest approach is to keep the product in the current state, but the product can become really big. So the smarter approach is instead of the product ~p~, keep ~\gcd(p, k)~. Notice that a number ~p~ is divisible by ~k~ if and only if ~\gcd(p, k) = k~. Notice the following (the proof is left as an exercise to the reader):

$$\displaystyle \gcd(pq, k) = \gcd(\gcd(p, k) \cdot \gcd(q, k), k)$$

So let us define ~dp_{i,j,g}~ as the number of paths starting at the upper left cell and ending at the cell ~(i, j)~ such that the greatest common divisor of the product of the numbers on the candy and ~k~ is equal to ~g~. Now it is easy to see the relation. We shall analyse the time complexity. Notice that all numbers smaller than ~10^6~ have at most ~300~ divisors, which means at most ~300~ different values of ~g = \gcd(p, k)~. So the number of states is ~\mathcal{O}(300 \cdot N^2)~ which is enough with a constant relation.