提示: 欢迎访问OurACM平台。
Problem 2236 第十四个目标

Accept: 152    Submit: 488
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

目暮警官、妃英里、阿笠博士等人接连遭到不明身份之人的暗算,柯南追踪伤害阿笠博士的凶手,根据几起案件现场留下的线索发现凶手按照扑克牌的顺序行凶。在经过一系列的推理后,柯南发现受害者的名字均包含扑克牌的数值,且扑克牌的大小是严格递增的,此外遇害者与毛利小五郎有关。

为了避免下一个遇害者的出现,柯南将可能遭到暗算的人中的数字按关联程度排列了出来,即顺序不可改变。柯南需要知道共有多少种可能结果,满足受害人名字出现的数字严格递增,但是他柯南要找出关键的证据所在,所以这个任务就交给你了。

(如果你看不懂上面在说什么,这题是求一个数列中严格递增子序列的个数。比如数列(1,3,2)的严格递增子序列有(1)、(3)、(2)、(1,3)、(1,2),共5个。长得一样的但是位置不同的算不同的子序列,比如数列(3,3)的答案是2。)

Input

多组数据(<=10),处理到EOF。

第一行输入正整数N(N≤100 000),表示共有N个人。

第二行共有N个整数Ai(1≤Ai≤10^9),表示第i个人名字中的数字。

Output

每组数据输出一个整数,表示所有可能的结果。由于结果可能较大,对1 000 000 007取模后输出。

Sample Input

3 1 3 2

Sample Output

5

Source

福州大学第十三届程序设计竞赛

Submit  Back  Status  Discuss