中文
日本語
English
| P4797串珠子 加强版 | ||
|
问题描述
铭铭有n个十分漂亮的珠子和若干根颜色不同的绳子。现在铭铭想用绳子把所有的珠子连接成一个整体。
现在已知所有珠子互不相同，用整数1到n编号。对于第i个珠子和第j个珠子，可以选择不用绳子连接，或者在ci,j根不同颜色的绳子中选择一根将它们连接。如果把珠子看作点，把绳子看作边，将所有珠子连成一个整体即为所有点构成一个连通图。特别地，珠子不能和自己连接。
铭铭希望知道总共有多少种不同的方案将所有珠子连成一个整体。由于答案可能很大，因此只需输出答案对1000000007取模的结果。
输入格式
第一行包含一个正整数n，表示珠子的个数。
接下来n行，每行包含n个非负整数，用空格隔开。
这n行中，第i行第j个数为ci,j。
输出格式
输出一行一个整数，为连接方案数对1000000007取模的结果。
样例输入 1
3
0 2 3
2 0 4
3 4 0
样例输出 1
50
样例输入 2
20
0 8 2 4 8 9 7 1 2 6 9 1 6 8 7 3 8 2 2 2
8 0 3 9 8 9 9 4 1 8 4 5 7 6 7 7 8 4 1 2
2 3 0 2 3 8 6 8 4 7 4 1 6 5 3 6 9 3 1 1
4 9 2 0 4 7 5 5 1 5 9 3 1 3 9 9 3 1 7 5
8 8 3 4 0 4 6 2 8 1 2 3 3 2 1 8 9 3 7 2
9 9 8 7 4 0 5 7 9 7 9 7 8 7 2 7 5 6 8 1
7 9 6 5 6 5 0 3 9 6 1 1 5 9 2 9 2 4 5 9
1 4 8 5 2 7 3 0 2 1 8 9 4 9 2 5 4 9 9 6
2 1 4 1 8 9 9 2 0 7 9 7 8 6 7 2 9 7 4 5
6 8 7 5 1 7 6 1 7 0 7 7 3 5 7 4 4 9 4 8
9 4 4 9 2 9 1 8 9 7 0 3 3 7 9 5 6 5 2 6
1 5 1 3 3 7 1 9 7 7 3 0 8 7 3 3 9 6 1 2
6 7 6 1 3 8 5 4 8 3 3 8 0 3 4 8 7 1 8 7
8 6 5 3 2 7 9 9 6 5 7 7 3 0 7 5 9 3 5 2
7 7 3 9 1 2 2 2 7 7 9 3 4 7 0 6 8 2 6 8
3 7 6 9 8 7 9 5 2 4 5 3 8 5 6 0 6 2 5 6
8 8 9 3 9 5 2 4 9 4 6 9 7 9 8 6 0 5 5 9
2 4 3 1 3 6 4 9 7 9 5 6 1 3 2 2 5 0 4 2
2 1 1 7 7 8 5 9 4 4 2 1 8 5 6 5 5 4 0 6
2 2 1 5 2 1 9 6 5 8 6 2 7 2 8 6 9 2 6 0
样例输出 2
160492041
提示
$0\leq c_{i,j}=c_{j,i}\lt 10^9+7$ ， \(c_{i,i}=0\)
五个测试点分别 \(n=16,17,18,19,20\) ，每组时限4秒，总时限10秒