U393599 小O的积木

如果这题有能通过更多数据，用更少空间、数据有锅、样例太弱请私信出题人

小O是一个积木爱好者，他想搭出不同形态的积木,可他搭积木空间有限长度不能超过在N宽度不能超过M高度不能超过K，且小O是一个强迫症晚期患者，第一层每一行只能是一条积木组成的线且必须和上一层有相接的，且积木不能浮空。即使作为积木爱好者小O的积木数量也是有限的所以用的积木数量不能超过Q，现在小O好奇在有限的空间内自己打出的积木有多少种本质不同的形态（整体平移本质上是相同的），可由于数量实在是太大所以你只要告诉他对1e9+7取余的结果即可

共1行M，N，K，Q

一行方案数对1e9+7取模

样例1的部分解释(0代表摆,1代表不摆) 下列两种第一层摆放方式本质是相同de | | | | | -----------: | -----------: | -----------: | |0 | 1 | 1 | | 0| 0 | 1 | | | | | | -----------: | -----------: | -----------: | | 1 | 1 | 0 | | 0 | 1 | 0 | 因为上面的可以通过平移得到下面的 第一层下列方式是不合法的 | | | | | -----------: | -----------: | -----------: | |1 | 0 | 0 | | 0 | 1 | 1 | 因为第一行第二行之间没有相接的面 | | | | | | :----------- | :----------- | :----------- | :----------- | |数据编号|N,K,K |Q|特殊性质 | | 1,2 |