Description

一套积木有三种形状，I 型积木由 2 个正方体组成：；L型积木由 3 个正方体组成： ；Y型积木由 4 个正方体组成： 。

利用这三种积木在一个以构成积木的正方体棱长为单位的 2 × m 区域上方堆出一个特定的形状，要求任何正方体的下方没有空隙。积木个数不限且可以任意翻转，有多少种不同的方法？

不同方法的定义：假如将区域上方每个单位正方体位置进行唯一编号，两种方法至少有一个编号位的覆盖积木类型或方位不同，则视为不同的方法。

Input

不超过50组测试数据，每组数据 3 行，第一行一个整数m，表示一个 2 × m 的区域。

第2、3行分别有 m 个整数 h_i, j，表示目标形状在区域第 i 行第 j 列上方以正方体棱长为单位的高度。

其中1 ≤ m ≤ 6，0 ≤ h_i, j ≤ 20，∑h_i, j > 0。

Output

每组数据输出对10⁹ + 7取模的方法数。

Sample

2
1 2
2 1
5
3 4 4 4 4
1 4 2 3 3

4
19818537

Hint