题目描述

Marton 的朋友 Cero 有一个由$N$个正整数组成的数组。

首先 Cero 会在黑板上写下这个数组中的第一个数字。接下来他会在之前写的某一个数字的左边或者右边写下一个数字。重复以上操作得到一个序列。

请注意，根据上述方法构造出的两个序列相同当且仅当每一个数字写下的顺序完全相同。例如，$1,1$可能和$1,1$不同，前者的第二个数在第一个数的左边，后者的第二个数在第一个数的右边。

求这些数组成的所有排列中，最长的严格递增子序列长度和此长度下的不同子序列个数。考虑到不同子序列个数很大，Marton 只想知道这个数对$10^9+7$取模的值。

输入输出格式

输入格式

第一行包含一个正整数$N$。

接下来的一行包含$N$个正整数，表示按顺序给出的这个数组的各个元素。

输出格式

仅一行，输出这个最长的子序列长度以及总个数模上$10^9+7$的值。

输入输出样例

输入样例 #1

2
1 1

输出样例 #1

1 4

输入样例 #2

4
2 1 3 4

输出样例 #2

4 1

说明/提示

样例解释

样例 1 解释

Cero 可以构造$2$个不同的序列，$1,1$和$1,1$。

显然最长的严格上升子序列长度为$1$，有$4$个子序列满足。

样例 2 解释

Cero 可以构造出$8$个不同的序列。最长的严格上升子序列长度为$4$，只有$1,2,3,4$满足。

数据规模与约定

对于$30\%$的数据，满足$N\le 20$。

对于$50\%$的数据，满足$N\le 10^3$。

对于$100\%$的数据，满足$N\le 2 \times10^5$，数组中的每个元素$\le10^9$。