题目描述

小 A 有 N 个正整数，他打算依次在黑板上写下这 N 个数。对于每一个数，他可以决定将这个数写在当前数列的最左边或最右边。

他想知道：

1. 写下的数列的可能的最长严格上升子序列（可由不连续的元素组成）的长度是多少；
2. 有多少种不同的最长的严格上升子序列。

两个子序列被认为是不同的，当且仅当：

• 两个子序列属于两个不同的写序列方案（两个写序列中有至少一步是不一样的）；
• 或两个子序列位于同一写序列方案的不同位置。

由于结果可能很大，只需要输出最长严格上升子序列的方案数对 (10^9 + 7) 取模的结果。

输入格式

• 第一行一个整数 N。
• 第二行 N 个正整数，表示小 A 写下的初始序列。

输出格式

输出一行两个整数：

1. 最长严格上升子序列的长度；
2. 方案数模 (10^9 + 7) 后的结果。

样例

样例 1

输入

2
1 1

输出

1 4

样例 2

输入

4
2 1 3 4

输出

4 1

数据范围与提示

• 对于 30% 的数据，N≤20；
• 对于 50% 的数据，1≤N≤1000；
• 对于 100% 的数据，1≤N≤200000。