题目描述

喵喵喵幼儿园有 $n$ 名同学，现在有 $n$ 个礼物要分配给他们，但是每个同学的喜好不同，具体地，第 $i$ 名同学最喜欢第 $p_{i,1}$ 个礼物，其次喜欢第 $p_{i,2}$ 个礼物……最不喜欢第 $p_{i,n}$ 个礼物，保证 $p_{i}$ 是一个 $1$ 到 $n$ 的排列。

现在懒惰的老师只给第 $i$ 名同学分配了第 $i$ 个礼物，他们自然希望通过交换来得到自己更喜欢的礼物，也就是说，交换结束之后每个人都不会拿到自己更不喜欢的礼物。

现在你需要帮助同学们完成交换礼物的过程，好奇的他们希望知道有多少种方法可以使得交换之后每个人都不会拿到自己更不喜欢的礼物。

正当你开始准备解决这个问题时，老师告诉你，同学们之间被分为了两个阵营，只有同一个阵营的同学之间才能交换礼物；并且这个阵营情况是会发生变化的，你需要对于 $q$ 种阵营情况分别求出只在同阵营的同学之间交换礼物，且交换之后合法的方案数，由于答案可能很大，所以你不需要取模再输出。

输入格式

第一行一个整数 $n$。

接下来 $n$ 行，第 $i+1$ 行 $n$ 个整数表示 $p_{i,1\cdots n}$。

接下来一行一个整数 $q$。

接下来 $q$ 行，每行一个长度为 $n$ 的字符串，若第 $i$ 个字符为 H，则第 $i$ 名同学属于第一个阵营，否则属于第二个阵营。

输出格式

共 $q$ 行，每行一个整数表示答案。

样例输入与输出

4
1 2 3 4
1 3 2 4
1 2 3 4
1 2 3 4
5
HHHH
HHGG
GHGH
HGGG
GHHG

2
1
1
2
2

见附件: gift2.in

见附件: gift2.out

数据规模与约定

对于所有数据，$1\leq n\leq 18$，$1\leq q\leq \min\{10^5,2^n\}$，保证 $p_i$ 是一个 $1$ 到 $n$ 的排列。

共 $18$ 组数据，第一组数据为样例，每个测试点基本等分（存在至多 1 分的差别）。

对于第 $i$ 组数据，$2\leq i\leq 13$，满足 $n=i+4$；

对于第 $i$ 组数据，$14\leq i\leq 18$，满足 $n=18$。