题目描述

洛克人又来拯救世界了。他的目的是杀死 Wily 博士做的机器人。在这个任务里，他将要试着摧毁一些机器人。
一开始，洛克人有一个叫巨型炸弹的武器，可以用来摧毁机器人。不幸的是，一个武器只能打倒一些特定机器人。然而，幸运的是，他可以使用他已经摧毁了的机器人的武器。注意，每个带武器的机器人只会带一个武器。洛克人身上只要有武器就能打到一个特定的机器人。
在这个问题中，告诉你关于机器人及其武器的信息，你需要计算出洛克人完成任务的顺序的方案数。
（因为是英文题目翻译而来，怕叙述不清楚，再说说大意：一开始你有一个武器，然后每个机器人也有一个武器，所有的武器都可以摧毁一些特定的机器人，你可以得到你摧毁的机器人身上的武器。问消灭所有机器人的方案数是多少，即有多少种不同的顺序）。

输入格式

第一行一个整数T，表示 T 组数据。
对于每组数据第一行一个整数 N，表示 N 个机器人（编号从 1 到 N），接下来 N + 1 行每行 N 个数字（0 或 1），即一个 (N+1) * N 的矩阵，每个数字表示为 Cij，行号从 0 到 N，列号从 1 到 N。第 0 行代表武器巨型炸弹的信息 C0j，C0j 为 1 表示巨型炸弹可以摧毁第 j 个机器人。接下来 N 行，Cij = 1 表示第 i 个机器人的武器可以摧毁第 j 个机器人。
注意，一个机器人的武器可以用来摧毁自己，但是这对题目没有什么影响，因为只有机器人已经被摧毁了，洛克人才能得他的武器。

输出格式

对于每组数据输出一行，即洛克人摧毁机器人的顺序方案总数。

样例输入

3
1
1
1
2
11
01
10
3
110
011
100
000

样例输出

1
2
3

数据范围

对于 50%的数据 T <= 10, 1 <= N <= 5
对于 100%的数据 T <= 50, 1 <= N <= 16

限制

1s

样例解释

对于样例3：
    摧毁顺序    开始 第一次后 第二次后 第三次后
    (1, 2, 3)  110   111     111     111
    (1, 3, 2)  110   111     111     111
    (2, 1, 3)  110   110     111     111
    (2, 3, 1)  110   110    无法打3
    (3, 1, 2)  110  无法打3
    (3, 1, 2)  110  无法打3
故答案为3

来源

UVa11795
CWOI新高二专题测试四