选牌

题目描述

Y 同学有一排共 $n$ 个位置，保证 $n$ 为偶数。每个位置上放着两张牌：

• 上方的牌数值为 $a_i$；
• 下方的牌数值为 $b_i$。

现在 Y 同学需要从每个位置中选择一张牌，组成一个长度为 $n$ 的序列 $c$。

也就是说，对于每个位置 $i$，可以选择：

• $c_i=a_i$；
• 或者 $c_i=b_i$。

要求最终得到的序列 $c$ 是一个回文序列，即对于所有 $1\le i\le n$，都满足 $c_i=c_{n+1-i}$。

请你计算一共有多少种选择方案。

注意：如果某个位置的两张牌数值相同，选择上方牌和选择下方牌仍然算作两种不同的选择方案。

由于答案可能很大，请输出答案对 $1000000$ 取模后的结果。

输入格式

第一行输入一个正整数 $n$，表示位置数量。

第二行输入 $n$ 个正整数 $a_1,a_2,\ldots,a_n$，表示每个位置上方牌的数值。

第三行输入 $n$ 个正整数 $b_1,b_2,\ldots,b_n$，表示每个位置下方牌的数值。

输出格式

输出一行一个整数，表示选择方案数对 $1000000$ 取模后的结果。

样例输入 #1

4
1 2 2 1
3 4 4 3

样例输出 #1

4

样例解释

第 $1$ 个位置和第 $4$ 个位置需要相等：

• 可以都选择数值 $1$；
• 也可以都选择数值 $3$。

所以这一对有 $2$ 种方案。

第 $2$ 个位置和第 $3$ 个位置需要相等：

• 可以都选择数值 $2$；
• 也可以都选择数值 $4$。

所以这一对也有 $2$ 种方案。

总方案数为 $2\times 2=4$。

样例输入 #2

6
1 2 3 3 2 1
1 5 6 6 5 1

样例输出 #2

16

样例解释

对于第 $1$ 个位置和第 $6$ 个位置：

• 第 $1$ 个位置两张牌都是 $1$；
• 第 $6$ 个位置两张牌也都是 $1$。

虽然数值相同，但选择上方牌和下方牌是不同方案，因此这一对位置共有 $4$ 种选择方式。

第 $2$ 个位置和第 $5$ 个位置有 $2$ 种方案。

第 $3$ 个位置和第 $4$ 个位置有 $2$ 种方案。

所以总方案数为 $4\times 2\times 2=16$。

样例输入 #3

4
1 2 3 4
5 6 7 8

样例输出 #3

0

样例解释

第 $1$ 个位置和第 $4$ 个位置无法选择出相同的数值，因此不存在合法方案。

数据范围

对于全部数据，满足：$2\le n\le 10^6$,$n$ 为偶数,$1\le a_i,b_i\le 10^9$。

本题共有 $10$ 个测试点，具体如下：