Marton 的朋友 Cero 有一个由 $N$ 个正整数组成的数组。最开始，Cero 在黑板上写下第一个数。然后，他将第二个数写在第一个数的左边或右边。之后，他将第三个数写在目前已写下的所有数字的左边或右边，依此类推。

Marton 问 Cero，能够得到的（不一定连续的）最长严格单调递增子序列的最大可能长度是多少。

他还想知道这种最长严格单调递增子序列的数量。更具体地说，如果最长严格递增子序列的长度为 $M$，他想知道对于 Cero 可以构造出的每一种可能的序列，其中长度为 $M$ 的严格递增子序列的数量之和。如果构造序列时的移动顺序不同，则认为构造出的序列是不同的；如果构造出的序列中的子序列在至少一个位置上不同，则认为它们是不同的子序列。

鉴于此类子序列的数量可能非常大，Marton 只需要该数量对 $10^9 + 7$ 取模后的结果。

Cero 现在实在没有时间来寻找 Marton 问题的答案，所以他请求你帮他解决这个问题。

输入格式

输入的第一行包含一个整数 $N$（$1 \le N \le 2 \times 10^5$）。

第二行包含 $N$ 个空格分隔的整数，表示 Cero 数组中的元素。输入中的每个数字都小于或等于 $10^9$。

输出格式

你必须在单行中输出两个整数，分别表示最长严格单调递增子序列的长度，以及该长度的严格递增子序列的总数对 $10^9 + 7$ 取模后的结果。

子任务

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

对于 $50\%$ 的测试数据，满足 $N \le 1000$。

样例

输入样例 1

2
1 1

输出样例 1

1 4

输入样例 2

4
2 1 3 4

输出样例 2

4 1

说明

样例 1 解释：

能够得到的最长严格单调递增子序列的长度为 $1$，共有 $4$ 个。

第一种可能的构造方式：写下第一个 $1$，将第二个 $1$ 写在右边：得到的序列为 $1, 1$；其中有两个长度为 $1$ 的严格递增子序列：$\underline{1}\ 1$ 和 $1\ \underline{1}$。

第二种可能的构造方式：写下第一个 $1$，将第二个 $1$ 写在左边：得到的序列为 $1, 1$；其中有两个长度为 $1$ 的严格递增子序列：$\underline{1}\ 1$ 和 $1\ \underline{1}$。

样例 2 解释：

能够得到的最长严格单调递增子序列的长度为 $4$。

只有当他构造出序列 $1\ 2\ 3\ 4$ 时才能得到该长度。在这种构造方式中，它是唯一一个长度为 $4$ 的严格递增子序列，因此这样的子序列数量为 $1$。