//MULDATATYPE为矩阵元素类型,MAXMAT为最大矩阵大小

typedef long MULDATATYPE;
#define MAXMAT 100
#define inf 1000000000

#define fabs(x) ((x)>0?(x):-(x))
#define zero(x) (fabs(x)<1e-10)

struct mat
{
    long n,m;
    MULDATATYPE data[MAXMAT][MAXMAT];
    void operator =(const mat& a);
    mat operator +(const mat& a);
    mat operator -(const mat& a);
    //0-1邻接矩阵
    mat operator &(const mat& a);
    mat operator |(const mat& a);
};

//c=a*b
//注意引用
int Mat_MulMode(mat& c,const mat& a,const mat& b,MULDATATYPE mod)
{
    long i,j,k;
    if (a.m != b.n)
        return 0;
    c.n = a.n , c.m = b.m;
    for (i = 0 ; i < c.n ; i ++)
        for (j = 0 ; j < c.m ; j ++)
            for (c.data[i][j] = k = 0 ; k  < a.m ; k ++)
                c.data[i][j] = (c.data[i][j] + a.data[i][k] * b.data[k][j]) % mod;
    return 1;
}
//c=a^b(其中必须满足b>0)
int Mat_PowMode(mat& c,mat a,long b,MULDATATYPE mod)
{
    c = a;
    b --;
    while(b)
    {
        mat tmp;
        if(b & 1)
        {
            tmp = c;
            Mat_MulMode(c,tmp,a,mod);
        }
        tmp = a;
        Mat_MulMode(a,tmp,tmp,mod);
        b = b>>1;
    }
    return 1;
}
//c=a+b
int Mat_AddMode(mat& c,const mat& a,const mat& b,MULDATATYPE mod)
{
    long i,j;
    if (a.n != b.n || a.m != b.m)
        return 0;
    c.n = a.n , c.m = b.m;
    for (i = 0 ; i < c.n ; i ++)
        for (j = 0 ; j < c.m ; j ++)
            c.data[i][j] = (a.data[i][j] + b.data[i][j]) % mod;
    return 1;
}
//c=a-b
int Mat_SubMode(mat& c,const mat& a,const mat& b,MULDATATYPE mod)
{
    long i,j;
    if (a.n != b.n || a.m != b.m)
        return 0;
    c.n = a.n , c.m = b.m;
    for (i = 0 ; i < c.n ; i ++)
        for (j = 0 ; j < c.m ; j ++)
            c.data[i][j] = (a.data[i][j] - b.data[i][j]) % mod;
    return 1;
}


void mat::operator =(const mat& a)
{
    n = a.n;
    m = a.m;
    for(int i = 0 ; i < n ; i ++)
        for(int j = 0 ; j < m ; j ++)
            data[i][j] = a.data[i][j];
}
mat mat::operator +(const mat &a)
{
    long i,j;
    mat tmpMat;
    tmpMat.m = m;
    tmpMat.n = n;
    for(i = 0 ; i < n ; i ++)
        for(j = 0 ; j < m ; j ++)
            tmpMat.data[i][j] = data[i][j] + a.data[i][j];
    return tmpMat;
}
mat mat::operator -(const mat &a)
{
    long i,j;
    mat tmpMat;
    tmpMat.m = m;
    tmpMat.n = n;
    for(i = 0 ; i < n ; i ++)
        for(j = 0 ; j < m ; j ++)
            tmpMat.data[i][j] = data[i][j] - a.data[i][j];
    return tmpMat;
}
mat mat::operator &(const mat &a)
{
    long i,j;
    mat tmpMat;
    tmpMat.m = m;
    tmpMat.n = n;
    for(i = 0 ; i < n ; i ++)
        for(j = 0 ; j < m ; j ++)
            tmpMat.data[i][j] = data[i][j] & a.data[i][j];
    return tmpMat;
}
mat mat::operator |(const mat &a)
{
    long i,j;
    mat tmpMat;
    tmpMat.m = m;
    tmpMat.n = n;
    for(i = 0 ; i < n ; i ++)
        for(j = 0 ; j < m ; j ++)
            tmpMat.data[i][j] = data[i][j] | a.data[i][j];
    return tmpMat;
}