题目描述 小 H 是今年 HSPC 的总命题人。此次 HSPC 共有 4 4 题。

小 H 事先已向全社会征集了 � N 道备选试题。这些试题解法各异，有的只需要 C++ 编程语言基础，有的则需要事先掌握多种高级数据结构。根据备选试题所需运用的算法知识，命题委员会认为其中某些只适宜作为比赛的第一题，某些适宜做第二题或第四题……也有某些备选试题放到 4 4 题中的任意位置均可。

假设一套卷子必须 4 4 题齐备、各不相同，并且每道备选试题只能出现在它所适宜的位置上。请你帮小 H 计算总共有多少种合法的组卷方案。

输入格式 第一行，一个整数 � N，表示征集到的试题数量。

接下来 � N 行，每行 4 4 个整数 � � , 1 a i,1 ​ , � � , 2 a i,2 ​ , � � , 3 a i,3 ​ , � � , 4 a i,4 ​ ，依次描述每道备选试题的情况。 � � , � a i,j ​ 只有 1 1 或 0 0 两个可能的取值：

� � , � a i,j ​ 为 1 1 时，表示备选试题 � i 适宜作为比赛中的第 � j 题； � � , � a i,j ​ 为 0 0 时，表示备选试题 � i 不适宜作为比赛中的第 � j 题。 输出格式 一个整数，表示有多少种合法的组卷方案。输出结果请对 1 0 9 + 7 10 9 +7 取模。

注意：程序的中间运算结果可能会超出 int 范围。

输入输出样例 输入 #1复制 6 1 1 0 0 0 0 1 0 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 1 输出 #1复制 8 输入 #2复制 7 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 输出 #2复制 840 说明/提示 【样例解释# 1 1】

共有 8 8 种合法的组卷方案，分别是 ( 1 , 3 , 2 , 5 ) (1,3,2,5), ( 1 , 3 , 2 , 6 ) (1,3,2,6), ( 1 , 3 , 4 , 5 ) (1,3,4,5), ( 1 , 3 , 4 , 6 ) (1,3,4,6), ( 3 , 1 , 2 , 5 ) (3,1,2,5), ( 3 , 1 , 2 , 6 ) (3,1,2,6), ( 3 , 1 , 4 , 5 ) (3,1,4,5), ( 3 , 1 , 4 , 6 ) (3,1,4,6)。

其他组卷方案都是不合法的。例如方案 ( 1 , 2 , 4 , 5 ) (1,2,4,5) 中，备选试题 2 2 不适宜作为 4 4 题中的第 2 2 题，故方案不合法；方案 ( 3 , 3 , 2 , 6 ) (3,3,2,6) 中，备选试题 3 3 出现了两次，故方案不合法。

【样例解释# 2 2】

840 7×6×5×4=840。

【数据规模与约定】

对于 35 % 35% 的数据，保证 � ≤ 50 N≤50。

1 a i,j ​ =1（每道备选试题均适宜于 4 4 题中的任意位置）。

1 a i,1 ​ +a i,2 ​ +a i,3 ​ +a i,4 ​ =1（每道试题均只适宜于 4 4 题中的某单个位置）。

对于 100 % 100% 的数据，保证 4 ≤ � ≤ 100000 4≤N≤100000， 0 ≤ � � , � ≤ 1 0≤a i,j ​ ≤1。