题目描述

强哥是一位古董收藏家，他有n件珍贵的收藏品排成一列，每件收藏品的价值为 $a_i$。最近收藏品市场行情看涨，强哥发现这些收藏品的价值正在形成一段上升趋势。

强哥想知道，在这些收藏品中：

1. 最长的价值连续上升的收藏品序列有多长？
2. 这样的最长上升序列有多少种不同的方案？（只要序列中至少有一件收藏品不同，就认为是不同方案）

由于可能的最长上升子序列的方案太多，请将结果对 $10007$ 取模。

输入格式

第一行一个整数 $n$，表示收藏品数量 第二行 $n$ 个正整数，表示每件收藏品的价值

输出格式

一个整数，表示最长上升序列的不同方案数量（对 $10007$ 取模）

样例

5
1 3 5 4 7

2

数据范围

$1≤n≤2000$

$1≤a_i≤10^6$