Description

合唱队有$n$个成员，他们的身高参差不齐。想要站在学校的大舞台上演出，首先必须要排出一个看得顺眼的队形。我们称满足下面这样的队形是整齐的：

对于$k$个人排成的队伍，第$i$个人的身高为$h_i$，存在一个$1\le i\le k$，使得当$j<i$时，$h_j<h_{j+1}$，当$j>i$时，$h_j<h_{j-1}$。

合唱队的负责人还说，并不一定所有人都要在最终的队形中。

小W认为仅仅排出一个队形还是比较简单的，因此他在思考一个进一步的问题：

在最终队形中的人数分别为$1$~$n$时，分别有多少种排列方案使得队形是整齐的。两种排列方案不同当且仅当存在某个位置上的成员编号不同。

然而小W实在太菜了，无法得到这个问题的答案，于是小W把问题交给了你。

Format

Input

第一行输入一个整数$n$，表示合唱队成员的数目。

接下来一行，输入$n$个整数，其中第$i$个整数表示编号为$i$的成员的身高$h_i$。

Output

输出$n$行，每行输出一个整数，第$i$行输出当最终队形中人数为$i$时的合法方案数目。

因为答案可能很大，所以请你将其对$10^9+7$取模后输出。

Samples

3
1 2 1

3
4
2

Limitation

【样例解释】

合法的排列方案有：$1,2,3,12,21,23,32,123,321$。

其中每个数字串代表一种排列方案，数字串中的每个数字代表对应位置队员的编号。

【数据范围】

对于$30\%$的数据：$1\le n,h_i\le 10$。

对于$60\%$的数据：$1\le n,h_i\le 200$。

对于$100\%$的数据：$1\le n,h_i\le 2000$。