← 返回题目列表

AtCoder · utpc2014_g

G. 独特的组合

中文机器翻译题面 查看原题

問題

背景

你是一个综艺节目的制作人。在这个节目中,没有棒球经验的偶像女孩们在击球中心击出快球(预定数量)。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