题在被nodgd做。

nodgd正在做的这道题，给出了两个长度为 $2n$ 的序列 \(\\{a_1,a_2,\dots,a_{2n}\\},\ \\{b_1,b_2,\dots,b_{2n}\\}\) ，序列中每个数都是不超过 \(n\) 的正整数，且每个数都恰好出现了两次。

题目曾经被nodgd理解错。

nodgd错误的以为，题目需要计算两个序列的最长上升公共子序列的长度，以及有多少不同的最长上升公共子序列。

两个序列的一个公共子序列可以用每个数在原序列中的下标序列来表示：

其中 \(m\) 是公共子序列的长度，对于 \(k=1,2,\dots,m\) 都满足 \(a_{i_k}=b_{j_k}\) ，且下标序列单调递增，即

两个公共子序列不同，当且仅当对应的下标序列不同。

后来题目又被nodgd正确的理解了。

nodgd发现自己理解错题意之后，就把这个问题作为考试题拿来恶心你。考虑到不同的最长上升公共子序列的数量可能比较多，你只需要计算出答案 \(\bmod 1,000,000,009\) 之后的结果。

输入共三行。

第一行有一个整数 \(n\) ，含义如问题描述中所述。

第二行有 $2n$ 个整数 \(a_1,a_2,\dots,a_{2n}\) 表示第一个序列。

第三行有 $2n$ 个整数 \(b_1,b_2,\dots,b_{2n}\) 表示第二个序列。

输出共两行。

第一行有一个整数，是这两个序列的最长上升公共子序列的长度。

第二行有一个整数，是不同的最长上升公共子序列的数量 \(\bmod 1,000,000,009\) 后的结果。

输入输出样例1说明

最长上升公共子序列可以是 $1,3$ 或者 $2,3$ ，长度是 $2$ 。

形如 $1,3$ 的最长上升公共子序列有 $1$ 种，它的下标序列是

形如 $2,3$ 的最长上升公共子序列有 $8$ 种，它们的下标序列是

合计 $9$ 种不同的最长上升公共子序列。

数据规模与约定

前 $10\%$ 的数据， \(n\leq 5\) ；

前 $30\%$ 的数据， \(n\leq 12\) ；

前 $50\%$ 的数据， \(n\leq 100\) ;

前 $70\%$ 的数据，\(n\leq 1000\) ;

全部的测试数据， $1\leq n\leq 30000​$ 。