更好的阅读体验，请在https://github.com/hyandfhz/pic-bed/blob/master/files/%E4%BA%91%E6%A2%AF.md查看。

这是晴练P2876云梯的题面。原链接
unicornFairy开始了新的学期。学校换了一个新校长，随之而来的是周五放学的时间由晚上七点半延时到了晚上八点半。unicornFairy认为这很不公平，所以她准备抢先一步回家。晚饭后，unicornFairy来到了一处没有监控的围墙旁。
小马将援助unicornFairy逃出学紫。学校的校长办公室共有n块石砖，小马使用魔法将这些垫脚石按1−n的编号空投至unicornFairy的位置。规定每个垫脚石有一个特征值a[i]，这块垫脚石的长度和a[i]成反比例。unicornFairy需要将它们组成云梯。可惜unicornFairy实在是太娇弱了，她的手上同时只能拿一块垫脚石。对于每块符合要求的垫脚石，unicornFairy可以选择是否将其放在云梯顶端。为了防止云梯倒塌，放上去的垫脚石一定比前一块更长。不要的垫脚石会被立即销毁，防止校长发现。云梯的高度定义为这条云梯上所有的垫脚石的数量。unicornFairy现在很急！她需要一条最长的云梯的所有垫脚石的特征值序列 b[i]，使得垫脚石编号组成的序列的字典序最小。
现在请你帮助unicornFairy写一个程序，求出云梯的最大高度h，并且求出对应的特征值的序列 b[i]。由于这道题被大佬lzyqwq秒了，现在需要你求出所有组成高度为k的云梯的所有方案数。请注意，每块垫脚石都是不同的，意味着两种方案的云梯形状可能是相同的。方案数对1,000,000,007取模。（详见样例1）
第一行，一个正整数n，表示垫脚石的个数。
第二行，n个正整数a[i]，表示每个垫脚石的特征值a[i]。
第一行，一个正整数h，表示云梯最大的高度。
第二行，共h个正整数b[i]，表示unicornFairy放置垫脚石的方案。
第三行，一个正整数k，表示搭出高度为h的云梯的所有方案数。方案数对1,000,000,007取模。

6
13 3 3 2 4 19

3
3 4 19
3

通过计算可得最大高度h为3，b序列为3 4 19。 总共有三种方案：

10
7 2 4 4 9 9 1 0 5 2

3
2 4 9
6

50
33 38 39 27 6 41 16 5 39 49 10 37 24 30 19 32 32 30 27 29 12 43 42 20 27 42 11 30 35 7 16 23 18 40 21 17 26 34 4 10 48 44 46 24 33 24 2 45 50 46

11
6 16 24 27 29 30 35 40 44 46 50
45

• 对于数据点weak1～5，n≤20且a[i]≤50
• 对于数据点6~10，n≤100且a[i]≤10,000
• 对于数据点11~20，没有额外限制。
• 对于全部数据，保证n≤1,000,000并且a[i]≤1,000,000,000

提示：您可以使用快读降低程序输入常数。

inline int read() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0' && ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}