P6885 [COCI 2016/2017 #3] Zoltan

Marton 的朋友 Cero 有一个由 $N$ 个正整数组成的数组。 首先 Cero 会在黑板上写下这个数组中的第一个数字。接下来他会在之前写下的所有数的左边或者右边写下一个数字。重复以上操作得到一个序列。 请注意，根据上述方法构造出的两个序列相同**当且仅当每一个数字写下的顺序完全相同**。例如，$1,1$ 可能和 $1,1$ 不同，前者的第二个数在第一个数的左边，后者的第二个数在第一个数的右边。 求这些数组成的所有序列中，最长严格递增子序列长度的最大值 $M$，以及所有最长严格递增子序列长度等于 $M$ 的序列中，最长严格递增子序列个数的总和。考虑到答案可能很大，Marton 只想知道这个数对 $10^9+7$ 取模的值。

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

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

### 样例解释 #### 样例 1 解释 Cero 可以构造 $2$ 个不同的序列，$1,1$ 和 $1,1$。 显然最长的严格上升子序列长度为 $1$，有 $4$ 个子序列满足。 #### 样例 2 解释 最长的严格上升子序列长度为 $4$，只有 $1,2,3,4$ 满足。 ### 数据规模与约定 对于 $30\%$ 的数据，满足 $N\le 20$。 对于 $50\%$ 的数据，满足 $N\le 10^3$。 对于 $100\%$ 的数据，满足 $N\le 2\times10^5$，数组中的每个元素 $\le10^9$。 ### 说明 **题目译自 [COCI2016-2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #3](https://hsin.hr/coci/archive/2016_2017/contest3_tasks.pdf) _T5 Zoltan_**。 样例 1,2 的解释非官方。