题目背景

动态规划

题目描述

给定长度为nn的整数数列，求最长上升子序列的长度，以及方案数。

由于方案数可能很大，请输出答案模10^9 + 710
9
+7的结果。

输入格式

第一行包含整数\(nn\)。

第二行包含nn个整数，之间用空格隔开。

输出格式

只有一行，输出长度与方案数，之间用空格隔开。

输入输出样例

输入

6
1 8 2 6 3 9

输出

4 2

说明/提示
对于\(30%\)的数据，\(1 ≤ n ≤ 201≤n≤20\)。

对于\(100%\)的数据，\(1 ≤ n ≤ 20001≤n≤2000，1 \leq a_i \leq 10^91≤a i​ ≤10 9\)。