题目描述

强哥在大学里参加了一场编程比赛，比赛的内容与数字序列有关。
他发现生活中很多事情也像是一个数字序列：比如学习新知识，每天进步一点点，知识水平就在逐渐“上升”。
现在他面对一个具体的挑战：

给定一个长度为 $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$