Migrated from Lutece 3239 猫数

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

小 $w$ 爱玩怪猎。最近，他在怪猎交流群学到了一个神奇的仪式——“猫数仪式“来增加自己刷珠子的掉落率。

仪式流程如下：随机生成一个序列，计算出它的猫数，在公屏上打出猫数并请求猫猫保佑。

对于一个长度为 $2n-1$ 的数字序列 $a$ ，它的猫数是满足以下条件的序列 $b$ 的数量：

1. $b$ 的长度为 $n$ ；

2. $b_i = \{p_1\cdots p_{2i-1}\}$ 的中位数；

3. $p$ 为 $a$ 的一个排列。

但小 $w$ 不小心在打 mod 的时候删除了群友给的计算程序，请聪明的你帮他写一个程序计算猫数。

Input

第一行一个整数 $n$ ，表示给定序列的长度为 $2n-1$ 。

第二行 $2n-1$ 个整数，表示 $a_1,a_2,\cdots a_{2n-1}$ 。

Output

一个整数，表示猫数对 $10^9+7$ 取模后的结果。

Samples

2
1 3 2

3

4
1 3 2 3 2 4 3

16

15
1 5 9 11 1 19 17 18 20 1 14 3 3 8 19 15 16 29 10 2 4 13 6 12 7 15 16 1 1

911828634

Constraints

$1\leq n\leq 50$ , $1\leq a_i \leq 2n-1$.