#include<iostream>
using namespace std;
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int dp[101][101],po[101][101];
int i,j,k,p,t,n,m,x,y;
scanf("%d",&t);
while(t--)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
scanf("%d",&po[i][j]);
dp[i][j]=0;
}
dp[1][1]=1;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
for(k=0;k<=po[i][j];k++)
for(p=0;p<=po[i][j]-k;p++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(p==0&&k==0)
continue;
x=k+i;
y=p+j;
if(x>n||y>m)
continue;
dp[x][y]+=dp[i][j];
if(dp[x][y]>10000)
dp[x][y]%=10000;
}
}
printf("%d\n",dp[n][m]);
}
return 1;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)