对于 $k\le 20$ 的部分分我们有一个比较简单的动态规划做法：令 $f_{i,j,w}$ 为从 $(1,1)$ 走到 $(i,j)$ 且路径上乘积除以 $k$ 的余数为 $w$ 的方案数，对于 $a_{i,j}\ge 0$ 的 $(i,j)$ 显然有 $f_{i,j,x\times a_{i,j}\bmod k}=f_{i-1,j,x}+f_{i,j-1,x}$，答案为 $f_{n,n,0}$。

但 $k=10^6$ 的时候这个做法是 $O(n^2k)$ 的，无法通过。

维护余数肯定是不行了；那么换个角度想，让上文 $w$ 的含义变为路径上的乘积 $p$ 与 $k$ 的最大公约数 $\gcd(p,k)$：只有 $\gcd(p,k)=k$ 时才有 $k|p$。因为 $\gcd(p,k)|k$，所以第三维的大小为 $k$ 的因数个数，可以证明在 $k\le 10^6$ 的情况下不超过 $300$ 个。

在转移过程中求最大公约数的时候会带个 $\log$，会被卡。可以先预处理一下 $k$ 的所有因数两两之间乘积与 $k$ 的最大公约数，然后对于每个输入的 $a_{i,j}\ge 0$ 都执行 $a_{i,j}\leftarrow\gcd(a_{i,j},k)$。转移为 $f_{i,j,\gcd(x\times a_{i,j},k)}=f_{i-1,j,x}+f_{i,j-1,x}$。

对于每个因数映射下标，方便转移。设 $k$ 映射的下标是 $x$，则答案为 $f_{n,n,x}$。时间复杂度 $O(k+d^2\log k+n^2d)$，其中 $d=300$，可以通过。

$63\mathrm{pts}$ 部分分代码（第一种思路）：

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int main(){
  ios::sync_with_stdio(false);
  int n,k; cin>>n>>k;
  vector a(n,vector<int>(n));
  for(auto &i:a)for(auto &j:i)cin>>j;
  vector f(n,vector(n,vector<int>(k)));
  f[0][0][a[0][0]%k]=1;
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
      if(a[i][j]>=0)
        for(int l=0;l<k;l++){
          if(i)(f[i][j][1ll*l*a[i][j]%k]+=f[i-1][j][l])%=mod;
          if(j)(f[i][j][1ll*l*a[i][j]%k]+=f[i][j-1][l])%=mod;
        }
  cout<<f[n-1][n-1][0]<<endl;
  return 0;
}

$110\mathrm{pts}$ 满分代码（第二种思路）：

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int main(){
  ios::sync_with_stdio(false);
  int n,k; cin>>n>>k;
  vector<int> p,m(k+1);
  for(int i=1;i<=k;i++)
    if(!(k%i))m[i]=p.size(),p.emplace_back(i);
  vector g(p.size(),vector<int>(p.size()));
  for(int i=0;i<p.size();i++)
    for(int j=0;j<p.size();j++)
      g[i][j]=m[gcd(1ll*p[i]*p[j],k)];
  vector a(n,vector<int>(n));
  for(auto &i:a)for(auto &j:i)if(cin>>j;j>=0)j=m[gcd(j,k)];
  vector f(n,vector(n,vector<int>(p.size())));
  f[0][0][a[0][0]]=1;
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
      if(a[i][j]>=0)
        for(int l=0;l<p.size();l++){
          if(i)(f[i][j][g[l][a[i][j]]]+=f[i-1][j][l])%=mod;
          if(j)(f[i][j][g[l][a[i][j]]]+=f[i][j-1][l])%=mod;
        }
  cout<<f[n-1][n-1].back()<<endl;
  return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=998244353;
int n,k,a[510][510],id;
int dp[510][510][310],f[310][310];
ll p[510];
int fd(int x){
	return lower_bound(p+1,p+1+id,x)-p;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>a[i][j];
		}
	}
	for(int i=1;i*i<=k;i++){
		if(k%i==0){
			p[++id]=i;
			if(i*i!=k)p[++id]=k/i;
		}
	}
	sort(p+1,p+1+id);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(~a[i][j])a[i][j]=fd(__gcd(a[i][j],k));
		}
	}
	for(int i=1;i<=id;i++){
		for(int j=1;j<=id;j++){
			f[i][j]=fd(__gcd(p[i]*p[j],(ll)k));
		}
	}
	dp[1][1][a[1][1]]=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)if(~a[i][j]){
			for(int l=1;l<=id;l++){
				if((~a[i+1][j])&&i<n)dp[i+1][j][f[l][a[i+1][j]]]=(dp[i+1][j][f[l][a[i+1][j]]]+dp[i][j][l])%mod;
				if((~a[i][j+1])&&j<n)dp[i][j+1][f[l][a[i][j+1]]]=(dp[i][j+1][f[l][a[i][j+1]]]+dp[i][j][l])%mod;
			}
		}
	}
	cout<<dp[n][n][id];
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N=510,P=998244353;
int dp[N][N][310],f[310],len,a[N][N],b[N][N],mp[1000010];
signed main()
{
	int n;LL kk;cin>>n>>kk;
	for(int i=1;i<=kk;i++)if(kk%i==0)f[++len]=i,mp[i]=len;
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)
	{
		cin>>a[i][j];if(a[i][j]==-1)continue;
		int d=__gcd(kk,(LL)a[i][j]);
		b[i][j]=mp[d];
	}
	dp[1][1][b[1][1]]=1;
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(a[i][j]!=-1)for(int k=1;k<=len;k++)
	{
		if(i<n&&a[i+1][j]!=-1)
		{
			LL d=__gcd(1ll*f[k]*f[b[i+1][j]],kk);
			dp[i+1][j][mp[d]]=(dp[i+1][j][mp[d]]+dp[i][j][k])%P;
		}
		if(j<n&&a[i][j+1]!=-1)
		{
			LL d=__gcd(1ll*f[k]*f[b[i][j+1]],kk);
			dp[i][j+1][mp[d]]=(dp[i][j+1][mp[d]]+dp[i][j][k])%P;
		}
	}
	cout<<dp[n][n][len]<<'\n';
	return 0;
}