The Usual Note

The intended solution got TLE in Python, so we recommend submitting with PyPy.

Problem Statement

A point $P$ moves on a 3-dimensional grid according to the following rules.

• Initially, at time 0, the point $P$ is at the origin $(0, \ 0, \ 0)$.
• When the point $P$ is at the lattice point $(x, \ y, \ z)$ at time $t$, the position of the point $P$ at time $t + 1$ is one of the adjacent lattice points
  • $(x + 1, \ y, \ z)$
  • $(x, \ y + 1, \ z)$
  • $(x, \ y, \ z + 1)$
  • $(x - 1, \ y, \ z)$
  • $(x, \ y - 1, \ z)$
  • $(x, \ y, \ z - 1)$
  and the probability of moving to each of these points is $\displaystyle \frac{1}{6}$.

Let $p$ be the probability that the coordinates $(x, \ y, \ z)$ of the point $P$ at time $T$ satisfy $ \ d \leq ax + by + cz \leq e \ $. Then $6^T \times p$ is an integer.

Find $6^T \times p$ modulo $10^9 + 7$.

Input

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

The first line contains the time $T$ described in the problem statement.

The second line contains the parameters $a$, $b$, $c$, $d$, $e$ representing the condition in the problem statement, in this order, separated by single spaces.

All inputs are integers and satisfy the following constraints.

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

Output

Output $6^T \times p$ modulo $10^9 + 7$. Print a newline at the end.

Sample

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