Description

小明有许多潜在的天赋，他希望学习这些天赋来变得更强。正如许多游戏中一样，小明也有n种潜在的天赋，但有一些天赋必须是要有前置天赋才能够学习得到的。

也就是说，有一些天赋必须是要在学习了另一个天赋的条件下才能学习的。比如，要想学会"开炮"，必须先学会"开枪"。

一项天赋可能有多个前置天赋，但只需习得其中一个就可以学习这一项天赋。

上帝不想为难小明，于是小明天生就已经习得了1号天赋-----"打架"。于是小明想知道学习完这n种天赋的方案数，答案对1,000,000,007取模。

Input

第一行一个整数n。

接下来是一个n*n的01矩阵，第i行第j列为1表示习得天赋j的一个前置天赋为i。

数据保证第一列和主对角线全为0。

n<=300

Output

第一行一个整数，问题所求的方案数。

Sample Input

8

01111111

00101001

01010111

01001111

01110101

01110011

01111100

01110110

Sample Output

72373

Solution

终于来填矩阵树的坑了……

其实也没啥难的，就是高斯消元解个行列式就完了……（）

这个题其实是让你求以$1$为根的外向树生成树个数。

无向图生成树：度数矩阵-邻接矩阵

有向图外向生成树：入度矩阵-邻接矩阵

有向图内向生成树：出度矩阵-邻接矩阵

把这个矩阵删掉一行一列然后求出的行列式的值就是生成树个数。

注意有向图的生成树需要删除根所在的行列来计算行列式。

Code

1 #include
     
       2 #include
      
        3 #include
       
         4 #define N (309) 5 #define LL long long 6 #define MOD (1000000007) 7 using namespace std; 8  9 LL n,f[N][N];10 char s[N];11 12 LL inv(LL a)13 {14     LL ans=1,b=MOD-2;15     while (b)16     {17         if (b&1) ans=ans*a%MOD;18         a=a*a%MOD; b>>=1;19     }20     return ans;21 }22 23 void Gauss(LL n)24 {25     int w=1,ans=1;26     for (int i=1; i<=n; ++i)27     {28         int num=i;29         for (int j=i; j<=n; ++j)30             if (abs(f[j][i])>abs(f[num][i])) num=j;31         if (num!=i) swap(f[num],f[i]), w=-w;32         for (int j=i+1; j<=n; ++j)33         {34             int t=f[j][i]*inv(f[i][i])%MOD;35             for (int k=i; k<=n; ++k)36                 f[j][k]=(f[j][k]-t*f[i][k])%MOD;37         }38     }39     for (int i=1; i<=n; ++i)40         ans=ans*f[i][i]%MOD;41     ans=(ans*w%MOD+MOD)%MOD;42     printf("%lld\n",ans);43 }44 45 int main()46 {47     scanf("%lld",&n);48     for (int i=0; i