AT_arc020_4 [ARC020D] お菓子の国の旅行

[problemUrl]: https://atcoder.jp/contests/arc020/tasks/arc020_4 お菓子の国はとても細長い国です。お菓子の国には $ N $ 個の町があり、それらの町は一直線上に並んでいて、端から順番に $ 1 $ から $ N $ までの番号がついています。隣り合う町の間には道があり、町 $ i $ と 町 $ i+1 $ どうしを繋ぐ道の長さは $ D_i $ です。お菓子の国での移動手段はこれらの道しか存在しないため、町 $ a $, $ b $ ($ a\

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ K $ $ D_1 $ $ D_2 $ : $ D_{N-1} $ - $ 1 $ 行目には、お菓子の国にある町の個数を表す整数 $ N\ (2\ ≦\ N\ ≦\ 100) $ と Ant さんが大好きな数を表す整数 $ M\ (1\ ≦\ M\ ≦\ 30) $ と Ant さんが買おうと考えている砂糖の種類の数を表す整数 $ K\ (2\ ≦\ K\ ≦\ 10 $ かつ $ K\ ≦\ N) $ が空白区切りで与えられる。 - $ 2 $ 行目から $ N-1 $ 行では、隣り合う町どうしを繋ぐ道の長さが与えられる。このうち $ i $ 行目には、町 $ i $ と町 $ i+1 $ を繋ぐ道の長さを表す整数 $ D_i\ (1\ ≦\ D_i\ ≦\ M) $ が与えられる。

答えを $ 1000000007(10^9+7) $ で割った余りを $ 1 $ 行に出力せよ。出力の末尾に改行をいれること。

### 部分点 この問題には部分点が設定されている。 - $ N\ ≦\ 12 $ を満たすテストケースすべてに正解した場合は $ 30 $ 点が与えられる。 ### Sample Explanation 1 以下の $ 6 $ つの方法がある。 - 町 $ 1 $ → 町 $ 3 $ → 町 $ 2 $ の順で砂糖専門店に訪れる。 - 町 $ 2 $ → 町 $ 3 $ → 町 $ 1 $ の順で砂糖専門店に訪れる。 - 町 $ 2 $ → 町 $ 1 $ → 町 $ 4 $ の順で砂糖専門店に訪れる。 - 町 $ 4 $ → 町 $ 1 $ → 町 $ 2 $ の順で砂糖専門店に訪れる。 - 町 $ 2 $ → 町 $ 3 $ → 町 $ 4 $ の順で砂糖専門店に訪れる。 - 町 $ 4 $ → 町 $ 3 $ → 町 $ 2 $ の順で砂糖専門店に訪れる。 ### Sample Explanation 2 答えは非常に大きな数になることもあるため、$ 1000000007(10^9+7) $ で割った余りを計算することを忘れてはならない。