BZPRO
#4894. 天赋
内存限制：128 MiB
时间限制：10 Sec
提交
提交记录
讨论
题目描述
小明有许多潜在的天赋，他希望学习这些天赋来变得更强。正如许多游戏中一样，小明也有n种潜在的天赋，但有
一些天赋必须是要有前置天赋才能够学习得到的。也就是说，有一些天赋必须是要在学习了另一个天赋的条件下才
能学习的。比如，要想学会"开炮"，必须先学会"开枪"。一项天赋可能有多个前置天赋，但只需习得其中一个就可
以学习这一项天赋。上帝不想为难小明，于是小明天生就已经习得了1号天赋-----"打架"。于是小明想知道学习完
这n种天赋的方案数，答案对1,000,000,007取模。
输入格式
第一行一个整数n。
接下来是一个n*n的01矩阵，第i行第j列为1表示习得天赋j的一个前置天赋为i。
数据保证第一列和主对角线全为0。
n<=300
输出格式
第一行一个整数，问题所求的方案数。
样例
样例输入
8
01111111
00101001
01010111
01001111
01110101
01110011
01111100
01110110
样例输出
72373
数据范围与提示
BZPRO