题目描述

给定 $n$ 个 $1,2,\cdots n$ 的排列 $a_1,a_2,\cdots a_n$，记 $f(S)$ 为满足下列条件的 $n$ 元组 $(b_1,b_2,\cdots b_n)$ 个数：

• $b$ 为一个 $1,2,\cdots n$ 的排列
• b_i=i$ 或排列 $a_i$ 中，数 $b_i$ 在数 $i$ 之前

$q$ 组询问，每次给定一个集合 $S$，求 $f(S)$。

输入格式

第一行一个正整数 $n$。

后面 $n$ 行，其中第 $i$ 行 $n$ 个正整数 $a_{i,1},a_{i,2},\cdots a_{i,n}$，表示排列 $a_i$。

后面一行一个正整数 $q$。

此后 $q$ 行，每行一个长度为 $n$，字符集为 $\{0,1\}$ 的字符串 $T$，表示一组询问。其中 $i\isin S$ 当且仅当 $T$ 第 $i$ 位为1。不保证 $S$ 非空。

输出格式

对于每个询问，输出一行一个非负整数，表示答案。

样例

ex_npc1.in
4
1 2 3 4
1 3 2 4
1 2 3 4
1 2 3 4
5
1111
1100
0101
1000
0110
ex_npc1.out
2
1
1
2
2

ex_npc2.in/out 见下发文件。

数据范围

对于所有测试点，满足 $3 \le n \le 18$, $1 \le q \le 2*10^5$, $a_i$ 为一个 $1,2,\cdots n$ 的排列。

以下 $id$ 为测试点编号。

提示：答案显然不超过 $n!$