## 解法

frontier法っぽいDPをやるだけ。 $O(NMK^2)$。

## 実装

#include <array>
#include <iostream>
#include <vector>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
using ll = long long;
using namespace std;
template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }

/**
* in terminal: *--->
*
* out terminal: *---<
*
*            ,---<
* left loop: *
*            --->
*
*             <---,
* right loop:     *
*             >---
*/

constexpr int MOD = 1e9 + 7;
ll solve(int n, int m, int k, vector<int> const & d) {
constexpr int   NONE = 0;
constexpr int OPENED = 1;
constexpr int CLOSED = 2;
auto dp = vectors(n, k + 1, k + 1, m, array<array<ll, 3>, 3>());

REP (i, n - 1) {
dp[i][0][1][0][OPENED][  NONE] += 1;  // new in-terminal
dp[i][0][1][0][  NONE][OPENED] += 1;  // new out-terminal
dp[i][1][1][0][  NONE][  NONE] += 1;  // new left-loop
REP (loop, k) REP (visited, k) REP (dist, m) REP (in, 3) REP (out, 3) {
if (in == CLOSED and out == CLOSED) continue;
ll it = (dp[i][loop][visited][dist][in][out] %= MOD);
int cnt = 2 * loop + (in == OPENED) + (out == OPENED);
auto ndist = (dist + cnt * d[i]) % m;
dp[i + 1][loop][visited    ][ndist][in][out] += it;  // dosn't use the (i + 1)-th shop
dp[i + 1][loop][visited + 1][ndist][in][out] += cnt * it;  // use the (i + 1)-th shop through
dp[i + 1][loop + 1][visited + 1][ndist][in][out] += it;  // add left-loop
if (2 <= loop) {
dp[i + 1][loop - 1][visited + 1][ndist][in][out] += loop * (loop - 1) * it;  // connect two left-loops using a right-loop
}
if (1 <= loop and in == OPENED) {
dp[i + 1][loop - 1][visited + 1][ndist][in][out] += loop * it;  // extend in-terminal with left- and right- loops
}
if (1 <= loop and out == OPENED) {
dp[i + 1][loop - 1][visited + 1][ndist][in][out] += loop * it;  // extend out-terminal with left- and right- loops
}
if (in == NONE) {
dp[i + 1][loop][visited + 1][ndist][OPENED][out] += it;  // add in-terminal *--->
}
if (in == NONE and loop >= 1) {
dp[i + 1][loop - 1][visited + 1][ndist][OPENED][out] += loop * it;  // connect with in-terminal <---*
}
if (out == NONE) {
dp[i + 1][loop][visited + 1][ndist][in][OPENED] += it;  // add out-terminal *---<
}
if (out == NONE and loop >= 1) {
dp[i + 1][loop - 1][visited + 1][ndist][in][OPENED] += loop * it;  // connect in-terminal >---*
}
if (in == OPENED and out == NONE) {
dp[i + 1][loop][visited + 1][ndist][CLOSED][CLOSED] += it;  // close with new out-terminal
}
if (in == NONE and out == OPENED) {
dp[i + 1][loop][visited + 1][ndist][CLOSED][CLOSED] += it;  // close with new in-terminal
}
if (in == OPENED and out == OPENED) {
dp[i + 1][loop][visited + 1][ndist][CLOSED][CLOSED] += it;  // close in- and out- terminal using a right-loop
}
}
answer += dp[i + 1][0][k][0][CLOSED][CLOSED] % MOD;
}