いつもの

Python では想定解法で TLE したので、PyPy で提出することをお勧めします。

問題文

3 次元グリッド上を点 $P$ が以下の規則に従って動きます。

• 最初、時刻 0 において点 $P$ は原点 $(0,0,0)$ にある。
• 時刻 $t$ において点 $P$ が格子点 $(x,y,z)$ にあるとき、時刻 $t+1$ での点 $P$ の位置は、隣接する格子点
  • $(x+1,y,z)$
  • $(x,y+1,z)$
  • $(x,y,z+1)$
  • $(x-1,y,z)$
  • $(x,y-1,z)$
  • $(x,y,z-1)$
  のいずれかであり、また、これらの点に移動する確率は、それぞれ ${\displaystyle \frac{1}{6}}$ である。

このとき、点 $P$ の時刻 $T$ における座標 $(x,y,z)$ が $d\le ax+by+cz\le e$ を満たす確率を $p$ とおくと、$6^T\times p$ は整数になります。

$6^T\times p$ を ${10}^9+7$ で割った余りを求めてください。

入力

$T$
$a$ $b$ $c$ $d$ $e$

1 行目に、問題文中に示された時刻 $T$ が与えられます。

2 行目に、問題文中の条件を表すパラメータ $a$, $b$, $c$, $d$, $e$ がこの順で半角スペース区切りで与えられます。

入力は全て整数で、以下の制約を満たします。

• $1\le T\le 500$
• $|a|,|b|,|c|\le 20$
• $(a,b,c)\ne (0,0,0)$
• $-10000\le d\le e\le 10000$

出力

$6^T\times p$ を ${10}^9+7$ で割った余りを出力してください。最後に改行してください。

サンプル

1
1 0 0 1 1

1

3
-2 0 0 -4 2

202

6
1 -1 0 0 0

9024

120
12 -1 2 -1212 1212

504758737