# Yuki 612 Move on grid

Problem Description:
Initially you are at coordinate (0, 0, 0). At each second, you have equal probability to move yourself with vector (-a, 0, 0), (a, 0, 0), (0, -b, 0), (0, b, 0), (0, 0, -c), (0, 0, c). Given t, a, b, c, d, e, and let p be the probability that the sum of value in each dimension of your coordinate after t seconds being in between d and e, output 6^t * p, modulo 1e9 + 7.

Constraints:
T ≤ 500
max { abs(a), abs(b), abs(c) } ≤ 20
-10000 ≤ d ≤ e ≤ 10000

Solution:
Assume that it is on one dimension, the result will still be the same since we are only interested in its sum. We are only requested to output the number of ways so that the sum at the final state is in between d and e, modulo 1e9 + 7.

Code:

```#include <bits/stdc++.h>

const int MOD = 1e9 + 7;

int Dp(int t, int a, int b, int c, int d, int e) {
int maxabc = std::max({std::abs(a), std::abs(b), std::abs(c)});
std::vector<std::vector<int>> dp(2, std::vector<int>(2 * t * maxabc + 1));
dp[0][t * maxabc] = 1;
int trans[] = {-a, a, -b, b, -c, c};
for (int i = 0; i < t; ++i) {
std::fill(dp[~i & 1].begin(), dp[~i & 1].end(), 0);
for (int j = -i * maxabc; j <= i * maxabc; ++j) {
for (int k = 0; k < 6; ++k) {
(dp[~i & 1][t * maxabc + j + trans[k]] += dp[i & 1][t * maxabc + j]) %= MOD;
}
}
}
int res = 0;
for (int i = d; i <= e; ++i) {
if (t * maxabc + i < 0 || 2 * t * maxabc < t * maxabc + i) continue;
(res += dp[t & 1][t * maxabc + i]) %= MOD;
}
return res;
}

signed main() {
std::ios::sync_with_stdio(false);
int T;
std::cin >> T;
int A, B, C, D, E;
std::cin >> A >> B >> C >> D >> E;
std::cout << Dp(T, A, B, C, D, E) << std::endl;
return 0;
}
```