題目描述

某個廚師十分喜歡炮製pancake。每個pancake都是圓的，所以我們總可以用直徑來表示其大小。這一次，廚師依次製作了 n 個不同大小的pancake，並把它們一字排開在枱上。

廚師先拿出一個空碟子，再由左到右考慮這 n 個pancake：對每一個pancake他可以選擇把它疊到碟子上，也可以選擇暫時放棄這個pancake；如此考慮完 n 次後，碟子上便會有若干個pancake。如果這 n 個pancake是由下至上越來越小的話，廚師就會說疊起來的那堆pancake是「好看」的，因為由上至下看時我們剛好能清晰看見每一件pancake (沒有pancake被上面的遮蓋)。換句話說，廚師希望選出來的每個pancake都比上一個選出的小。例如當pancake直徑依次為 (6, 5, 2, 3) 時，(3), (2), (5), (6), (6, 3), (6, 2), (6, 5), (5, 2), (5, 3), (6, 5, 2), (6, 5, 3) 是所有合法的堆疊方法。注意每種方法都至少要疊上一個pancake。

此時廚師突發奇想，到底共有多少種方法可以疊出好看的pancake呢？無奈他覺得這個問題極難，所以選擇把重任交給你。由於總方法數可能很大，請輸出答案除以 10⁹+7 (一個質數) 的餘數。

(或者，一個較無趣的題目表達是: 給定一有 n 個互異正整數的序列，求其單調下降子序列的數目。)

輸入格式

第一行有一正整數 T (1 <= T <= 5)，表示接下來有 T 組獨立的測資。（需要應答 T 次）

每個測資共有兩行。第一行給定一個正整數 n ，表示pancake數目；第二行則給 n 個正整數 (以空格隔開)，其中第 i 個數為第 i 個做出的pancake的直徑 d_i。保證 d_i 兩兩不同。

1 <= n <= 10⁵, 1 <= d_i <= 10⁹。

輸出格式

共輸出 T 行，分別為 T 個測資的答案。對第 i 個測資輸出有多少種方法 (mod 10⁹+7) 可以使抽出來的pancake是好看的。

Samples

["4\r\n3\r\n3 2 1\r\n4\r\n1 2 4 3\r\n4\r\n2 3 1 4\r\n3\r\n2 1 3","5\r\n4\r\n6 5 2 3\r\n5\r\n9 7 5 4 2\r\n6\r\n1 2 3 4 7 9\r\n1\r\n9\r\n5\r\n4 3 1 2 5"]

["7\r\n5\r\n6\r\n4","11\r\n31\r\n6\r\n1\r\n12"]

提示

温馨提示：系統能根據完成程度給予部分分數，但若要完全解決這題需要能處理 n, d_i 較大的情況。

原始資料

• Zero1 題號：a593
• Hydro 題號：Z0593
• Locale：zh_TW
• Display：open