题目描述

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

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

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

求这些数组成的所有序列中，最长严格递增子序列长度的最大值 $M$，以及所有最长严格递增子序列长度等于 $M$ 的序列中，最长严格递增子序列个数的总和。考虑到答案可能很大，Marton 只想知道这个数对 $10^9+7$ 取模的值。

输入格式

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

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

输出格式

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

2
1 1 

1 4 

4
2 1 3 4 

4 1

提示

样例解释

样例 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 CONTEST #3 T5 Zoltan。

样例 1,2 的解释非官方。