题目描述

有 $n$ 个元素的数组 $a_1,a_2,a_3,\cdots,a_n$，求该数组的最长上升子序列的长度与方案数。因为方案数可能很大，你只需要输出方案数对 $10^9+7$ 取模的结果。

输入格式

第一行输入一个整数 $n$，表示数组长度。

第二行输入 $n$ 个整数 $a_1,a_2,\cdots,a_n$，表示数组中的每一个数。

输出格式

一行两个整数，表示最长上升子序列的长度与方案数，之间用空格隔开。其中，方案数对 $10^9+7$ 取模。

样例输入输出

5
1 2 8 6 4

3 3

说明/提示

样例解释

最长上升子序列的长度为 $3$，并且有 $3$ 个，分别为 $[1,2,8],[1,2,6],[1,2,4]$ 。

数据范围

对于 $30\%$ 的数据，$1\le n\le 20$

对于 $100\%$ 的数据，$1\le n\le 2000$，$a_i$ 在 int 范围之内。