序列计数

度度熊了解到，$1$,$2$,…,$n$ 的排列一共有 $n! = n \times (n-1) \times \cdots \times 1$ 个。现在度度熊从所有排列中等概率随机选出一个排列 $p_1$,$p_2$,…,$p_n$，你需要对 $k$=$1$,$2$,$3$,…,$n$ 分别求出长度为 $k$ 的上升子序列个数，也就是计算满足 $1 \leq a_1$ < $a_2$ < … < $a_k$ $\leq n $ 且 $p_{a_1}$ <$p_{a_2}$< … < $p_{a_k}$ 的 $k$ 元组 ($a_1$,$a_2$,…,$a_k$) 的个数。

由于结果可能很大，同时也是为了 ruin the legend， 你只需要输出结果对 $1000000007(=10^9+7)$ 取模后的值。

第一行包含一个整数 $T$，表示有 $T$ 组测试数据。

接下来依次描述 $T$ 组测试数据。对于每组测试数据：

第一行包含一个整数 $n$，表示排列的长度。

第二行包含 $n$ 个整数 $p_1$,$ p_2$, …, $p_n$，表示排列的 $n$ 个数。

保证 $ 1 \leq T \leq 100$，$1 \leq n \leq 10^4$，$T$ 组测试数据的 $n$ 之和 $\leq 10^5$，$p_1$,$p_2$,…,$p_n$ 是 $1$,$2$,…,$n$ 的一个排列。

除了样例，你可以认为给定的排列是从所有 $1$,$2$,…,$n$ 的排列中等概率随机选出的。

对于每组测试数据，输出一行信息 "Case #x: $c_1$ $c_2$ ... $c_n$"（不含引号），其中 x 表示这是第 $x$ 组测试数据，$c_i$ 表示长度为 $i$ 的上升子序列个数对 $1000000007(=10^9+7)$ 取模后的值，相邻的两个数中间用一个空格隔开，行末不要有多余空格。

2
4
1 2 3 4
4
1 3 2 4

Case #1: 4 6 4 1
Case #2: 4 5 2 0

2018"百度之星"程序设计大赛 - 资格赛