一道创新工场笔试题，求解~该怎么解决

一道创新工场笔试题，求解~
在一个A×B的棋盘上，左上角是（0,0），右下角是（A-1，B-1），你每一步只能从（x，y）到（x+1,y+2），（x+2,y+1），（x,y+1），（x+1,y）4个位置中的一个。求从左上角走到右下角的走法的数目。（这个数目可能很大，结果只需模10000007即可，1<=A,B<=1000000且1<=A×B<=1000000）

[解决办法]
好吧，如果非要取模的话

C/C++ code

#include<iostream>using namespace std;int func(int row, int col){    int *table = new int[(row + 2) * (col + 2)];    int i, j;    int res;        memset(table, 0, sizeof(int) * (row + 2) * (col + 2));        for (i = 1; i < (row + 2); ++i)    {        table[i * (col + 2) + 1] = 1;    }    for (i = 1; i < (col + 2); ++i)    {        table[(col + 2) + i] = 1;    }        for (i = 2; i < (row + 2); i++)    {        for (j = 2; j < (col + 2); j++)        {            table[i * (col + 2) + j] = table[i * (col + 2) + j - 1]                                    + table[(i - 1) * (col + 2) + j]                                    + table[(i - 1) * (col + 2) + j - 2]                                    + table[(i - 2) * (col + 2) + j - 1];                                                table[i * (col + 2) + j] %= 1000000;//只需要这条加上就可以了，到底是1000000还是10000007？        }    }        res = table[(row + 2) * (col + 2) - 1];        delete[]table;        return res;}int main(){    cout<<func(1000, 1000)<<endl;    system("pause");    return 0;}
[解决办法]
探讨

好吧，如果非要取模的话

C/C++ code


#include<iostream>

using namespace std;

int func(int row, int col)
{
    int *table = new int[(row + 2) * (col + 2)];
    int i, j;
    int res;
    
    mem……