Problem : 222 - G. 啵啵攻略

Problem Statistics

Solved Member: 21　　Submission: 98　　User Tried: 24

Statement:

於是，啵啵雞迷上了推倒蘿莉的遊戲。

給定一個數列，試問有多少種選法可以找出最長嚴格遞增序列(LIS，Longest Increasing Sequence)。

你可以假定數列是蘿莉大小，而啵啵雞喜歡從小蘿莉推到大蘿莉，試問啵啵雞有多少種攻略法。

Input:Output:

一個測試檔有多筆測試資料，第一行有一個正整數T表示測試資料數量。

對於每筆測試資料，第一行有一個數字n(1<=n<=250000)表示數列長度，第二行有n個正整數Vi(1 <= Vi <= n)。

為了避免答案過大，請輸出LIS個數 mod 1000000007後的結果。

Sample Input:Sample Output:

3
3
3 2 1
4
1 2 2 3
4
1 3 1 3

3
2
3

HINT:

對於30%的測資，1<=n<=514。
對於60%的測資，1<=n<=3000。
對於100%的測資，1<=n<=250000。

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0	1000ms	65536kb
1	1000ms	65536kb	10
2	1000ms	65536kb	10
3	1000ms	65536kb	10
4	1000ms	65536kb	10
5	1000ms	65536kb	10
6	1000ms	65536kb	10
7	1000ms	65536kb	10
8	2000ms	65536kb	10
9	3000ms	65536kb	10
10	4000ms	65536kb	10