该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

Sad是一个友好的出题人，为大家又准备了一道不是特别困难的问题。

题目描述

给定整数$n(1 \leq n \leq 100000)$，以及长为$n$ 的一个排列，你需要回答这个排列的最长递增子序列的个数。

名词解释：

子序列：数组的一个子序列是原始数组删除一些（也可以不删除）元素而不改变剩余元素相对位置形成的新数组

排列：一个长度为 $n$ 的排列是指的是一个 $1$ 到 $n$ 每个数字都恰好出现一次的序列，例如 $[2,1,3],[1,2,3,4],[1]$都是排列，$[1,3],[4,2,1],[2]$ 不是排列

输入格式

第一行输入一个整数$n(1 \leq n \leq 100000)$，表示排列长度。

第二行输入$n$ 个整数 $a_1,a_2,...,a_n$ 表示需要检查的排列。

输出格式

一个整数，表示该排列的最长递增子序列的个数。 由于答案可能很大，请输出答案对$10^9 + 7$取模的结果。

样例 #1

样例输入 #1

1
1

样例输出 #1

1

样例 #2

样例输入 #2

5
2 3 5 1 4

样例输出 #2

2