1459: splay1的蛇形路径
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：78
Solved：14
Description
现在有一个形似$ 3*n $矩阵($3$行$n$列)，由$ 1*1 $地板铺成的走廊。
你站在走廊的最左端。每块地板上标有一个正整数。
假定你位于的地板上所标的数字为 $a$ ，则你下一步选定的地板上所标的数字 $b$ 必须满足 $gcd(a,b)=1$ 。
此外，你必须按对角线方式行走。
我们以 $(i,j)$ 代表第 $i$ 行 $j$ 列的方格。
开始时，你可以随意在 $(1,1)，(2,1)，(3,1)$ 中选择一个方格作为起点。
$(1,i)和(3,i)$ 的下一步只能选 $(2,i+1)$
$(2,i)$ 的下一步可以在 $(1,i+1)$ 和 $(3,i+1)$ 中选择。
第 $n$ 列的方格都是终点。
如果两条行走路线任意一步所选的方格不同，我们视为这两条路线是不同的。
请你输出从起点到终点合理的不同路径数。
结果需要对 $10^9+7$ 取模。
你站在走廊的最左端。每块地板上标有一个正整数。
假定你位于的地板上所标的数字为 $a$ ，则你下一步选定的地板上所标的数字 $b$ 必须满足 $gcd(a,b)=1$ 。
此外，你必须按对角线方式行走。
我们以 $(i,j)$ 代表第 $i$ 行 $j$ 列的方格。
开始时，你可以随意在 $(1,1)，(2,1)，(3,1)$ 中选择一个方格作为起点。
$(1,i)和(3,i)$ 的下一步只能选 $(2,i+1)$
$(2,i)$ 的下一步可以在 $(1,i+1)$ 和 $(3,i+1)$ 中选择。
第 $n$ 列的方格都是终点。
如果两条行走路线任意一步所选的方格不同，我们视为这两条路线是不同的。
请你输出从起点到终点合理的不同路径数。
结果需要对 $10^9+7$ 取模。
Input
第一行，一个整数 $n$ 代表地板列数。
接下来三行，每行 $n$ 个整数。第 $i$ 行 $j$ 列的整数 $a_{i,j}$ 代表第 $i$ 行 $j$ 列的地板上标的数字。
数据范围：
$1 \le n \le 10^4$
$1 \le a_{i,j} \le 10^6$
接下来三行，每行 $n$ 个整数。第 $i$ 行 $j$ 列的整数 $a_{i,j}$ 代表第 $i$ 行 $j$ 列的地板上标的数字。
数据范围：
$1 \le n \le 10^4$
$1 \le a_{i,j} \le 10^6$
Output
一行，一个整数。代表起点到终点合理的不同路径数。
Sample Input Copy
4
1 2 3 4
2 2 3 4
1 2 3 6Sample Output Copy
4HINT
样例中，合法的路径分别为：
$(1,1)->(2,2)->(1,3)->(2,4)$
$(1,1)->(2,2)->(3,3)->(2,4)$
$(3,1)->(2,2)->(1,3)->(2,4)$
$(3,1)->(2,2)->(3,3)->(2,4)$
$(1,1)->(2,2)->(1,3)->(2,4)$
$(1,1)->(2,2)->(3,3)->(2,4)$
$(3,1)->(2,2)->(1,3)->(2,4)$
$(3,1)->(2,2)->(3,3)->(2,4)$