問題

背景

あなたは、あるバラエティ番組のプロデューサーである。この番組では、野球経験の無いアイドルの女の子たちが、バッティングセンターで剛速球を（予め定められた数）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

1行目には、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