問題
背景
你是一个综艺节目的制作人。在这个节目中,没有棒球经验的偶像女孩们在击球中心击出快球(预定数量)。P 表演者预测他们会击回多少个球。
此时,不是简单地预测每个偶像可以回击多少个球,而是选择一组偶像,并且该组中包含的偶像的孩子们回击的球总数是预定的数量。 如果匹配 X ,则认为是正确的。
我们目前正在记录每个偶像能够击中多少球的“击球结果”。一些偶像已经完成了挑战。这时候你可能会发现你回击的球总数是 我意识到我最终陷入了这样一种情况:有多种方法可以选择一个集合,例如 X ,或者根本没有。
当剩余偶像的记录完成时,回击的球总数为 “如何选择一个集合使得 X ” 正是 1 找出有多少个相同的“击球结果”。
課題
长度 小于或等于 n 整数序列 给出 a_i 。 表示a 的一些元素是 0 以上 P 您可以自由选择以下任意整数。此时,总和只是 X 变成 a 子序列的方法正是 1 找出选择整数的方法的数量,使得 除以 1,000,000,007 求余数。然而,当我们说子序列以相同的方式选择时,我们仅意味着组成子序列的元素的下标集合是相同的。
配点
200
入力
输入按以下格式给出。
n X P a_1 : a_n
第一行说:n、X、P 可以得到第 3写入整数。
继续 n 行有 a 的元素从头开始依次写成 1 行 1 个。? (问号)表示该元素可以自由选择整数。
制約
- 1 ≤ n ≤ 50
- 1 ≤ X ≤ 10
- 1 ≤ P ≤ 10
- a_i =
?或 至少 0 ≤ a_i ≤ P
出力
所求的值为 1 行输出。
入出力例
入力例1
3 5 4 1 4 ?
出力例1
2
入力例2
3 5 5 ? 1 ?
出力例2
15