問題文

お菓子の国はとても細長い国です。お菓子の国には N 個の町があり、それらの町は一直線上に並んでいて、端から順番に 1 から N までの番号がついています。隣り合う町の間には道があり、町 i と 町 i+1 どうしを繋ぐ道の長さは D_i です。お菓子の国での移動手段はこれらの道しか存在しないため、町 a, b (a < b) について、町 a から町 b への移動距離と町 b から町 a の移動距離はいずれも D_a + D_{a+1} + ... + D_{b-1} となります。それぞれの町には砂糖専門店が 1 つずつあり、それぞれの砂糖専門店では他の町のものとは異なる砂糖を 1 種類売っています。ある町を訪れた際には、必ずその町の砂糖専門店で売っている砂糖を買わなければなりません。

アリ王国に住んでいるアリの Ant さんは、甘いものと数字の M が大好きです。Ant さんは今、お菓子の国へ旅行に行ってちょうど K 種類の砂糖を買いたいと考えています。Ant さんは、どの町の砂糖専門店をどの順番で訪れるのかを決めるために、まずはお菓子の国での移動距離の総和が M の倍数である町の訪れ方が何通りあるのかを計算してみることにしました。ただし、町の間の移動は遠回りをしないこととします。また、最初に訪れる町と最後に訪れる町はどこでも良いものとします。同じ町に2度訪れることはありません。町間の移動途中である町を通過したとして、その町を訪れたことにはならないことに注意してください。

Ant さんのために、お菓子の国での移動距離の総和が M の倍数となる町の訪れ方の個数を求めるプログラムを作ってあげて下さい。ただし、答えは非常に大きな数になることがあるため、1000000007(10^9+7) で割った余りを出力して下さい。

入力例1

4 4 3
2
1
3

出力例1

6

以下の 6 つの方法がある。

• 町 1 → 町 3 → 町 2 の順で砂糖専門店に訪れる。
• 町 2 → 町 3 → 町 1 の順で砂糖専門店に訪れる。
• 町 2 → 町 1 → 町 4 の順で砂糖専門店に訪れる。
• 町 4 → 町 1 → 町 2 の順で砂糖専門店に訪れる。
• 町 2 → 町 3 → 町 4 の順で砂糖専門店に訪れる。
• 町 4 → 町 3 → 町 2 の順で砂糖専門店に訪れる。

入力例2

15 5 10
5
5
5
5
5
5
5
5
5
5
5
5
5
5

出力例2

897286330

答えは非常に大きな数になることもあるため、1000000007(10^9+7) で割った余りを計算することを忘れてはならない。