いつもの

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 \leq ax + by + cz \leq 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 \leq T \leq 500$
• $|a|, \ |b|, \ |c| \leq 20$
• $(a, \ b, \ c) \neq (0, \ 0, \ 0)$
• $-10000 \leq d \leq e \leq 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