提示: 欢迎访问OurACM平台。
Problem 2126 消去游戏

Accept: 197    Submit: 495
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

S最近在玩一种游戏。这种游戏的规则是一个一个地往一个栈里放有颜色的球,当栈顶连续k个球颜色相同时,这k个球立刻同时消失。现在S已经往栈里放了n个球,他想知道再放m个球,然后使得栈里的球都被消去的放法有多少种。两种放法不同是指存在放的第i个球这两种放法放的球的颜色不同。由于方法数可能很多,将答案mod 1000000007。

Input

输入包含多组数据。输入数据的第一行为四个整数n,m,h,k(0<=n,m,h<=1000,2<=k<=1000),表示已经放了n个球,有h种不同颜色的球,若栈顶出现连续k个球颜色相同则这k个球同时消失,问再放m个球,使得最后栈里的球都被消去的放法数。第二行从左往右依次输入n个整数,范围为1到h,表示刚开始往栈里放的球的颜色,放入顺序与输入顺序相同,数据保证已经放入的n个球不会存在连续k个球颜色相同。答案对1000000007取余。

Output

输出一行一个整数M,表示对1000000007取余后的放法数。

Sample Input

3 6 3 3 1 2 2 0 6 2 3

Sample Output

9 8

Source

福州大学第十届程序设计竞赛

Submit  Back  Status  Discuss