题目描述

给你一个长度为 $n$ 的序列 $a$，你现在需要求出最长上升子序列的数量。

我们称两个最长上升子序列不同，当且仅当这两个子序列至少有一个元素的下标不同。

输入格式

第一行为一个整数 $n$，表示序列的长度。

第二行为 $n$ 个正整数，表示序列 $a$ 的所有元素。

输出格式

一个数，为序列的个数。序列个数可能非常多，所以你需要对 $10007$ 取模。

5
1 3 5 4 7

2

数据范围

$1\le n\le 2000, 1\le a_i\le 10^6$