移動したときに出てくる座標が少ない事がポイント． ただし，map を使って座標を記録すると重いので， 移動回数を状態に持ちながら dp.
解法0: DP
\(dp_{i,s,t} := \) \(i\) 回移動して，そのうち タイプ \(0\)の移動を \(s\) 回， タイプ \(1\)の移動を \(t\) 回 のときの場合の数
とする．タイプ \(2\) の移動は \(i-(s+t)\) 回と一意に定まるので， 状態として持っておく必要はない．
解法1: DP
こちらも DP だが，もっている状態が異なる．
\(dp_{s,t,u} := \) タイプ \(0\)の移動を \(s\) 回， タイプ \(1\)の移動を \(t\) 回 タイプ \(2\)の移動を \(u\) 回 のときの場合の数
とする．
自然に思いつくのは解法 \(0\). 実装が綺麗なのは 解法 \(1\). 解法 \(1\) の \(s,t,u\) は対称な条件だから，実装が綺麗に書ける．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
// 解法 0
int main() {
ll n, m ;
cin >> n >> m;
vvll move(3, vll(2));
rep(i,3){
cin >> move[i][0] >> move[i][1];
}
set<vll> p;
rep(i,m){
ll x,y; cin >> x >> y;
}
#define _rep(i,s) for (i = (0); i < (s); ++i)
dp[0][0] = 1;
rep(i,n) {
swap(old, dp);
vll s(3);
_rep(s[0],i+1) _rep(s[1],i+1){
s[2] = i - (s[0]+s[1]);
if(s[2] < 0) continue;
vll x(2), nx(2);
rep(xi,2) rep(k,3) x[xi] += s[k]*move[k][xi];
rep(k,3){
rep(xi,2) nx[xi] = x[xi] + move[k][xi];
if(!in(nx, p)){
ll ns0 = s[0], ns1 = s[1];
if(k == 0) ns0++;
else if(k == 1) ns1++;
dp[ns0][ns1] += old[s[0]][s[1]];
}
}
}
}
mint ans;
rep(s,n+1) rep(t,n+1){
ll u = n - (s+t);
if(u < 0) continue;
ans += dp[s][t];
}
cout << ans.val() << endl;
return 0;
}
// 解法 1
mint dp[305][305][305];
int main() {
ll n, m ;
cin >> n >> m;
vvll move(3, vll(2));
rep(i,3){
cin >> move[i][0] >> move[i][1];
}
set<vll> p;
rep(i,m){
ll x,y; cin >> x >> y;
}
#define _rep(i,s) for (i = (0); i < (s); ++i)
dp[0][0][0] = 1;
vll s(3);
_rep(s[0],n) _rep(s[1],n) _rep(s[2],n) if(s[0]+s[1]+s[2] < n){
vll x(2); rep(xi,2) rep(si,3) x[xi] += s[si]*move[si][xi];
rep(si,3){
vll ns = s;
ns[si]++;
vll nx(2); rep(xi,2) rep(si,3) nx[xi] += ns[si]*move[si][xi];
if(!in(nx, p)){
dp[ns[0]][ns[1]][ns[2]] += dp[s[0]][s[1]][s[2]];
}
}
}
mint ans;
rep(s,n+1) rep(t,n+1) rep(u,n+1) if(s+t+u == n) {
ans += dp[s][t][u];
}
cout << ans.val() << endl;
return 0;
}
