SolveMe

$N$개의 방이 있고, 각 방의 바닥에는 토끼 그림이 그려져 있다. 방 $r$의 토끼 그림 오른쪽 귀 부분에 올라가면, 방 $A[r]$에 그려진 토끼의 꼬리 위로 순간이동한다. 마찬가지로 방 $r$의 토끼 그림 왼쪽 귀 부분에 올라가면, 방 $B[r]$에 그려진 토끼의 꼬리 위로 순간이동한다.

정수 $X$, $Y$, $Z$가 주어진다. 고양이는 다음 조건을 만족하도록 순간이동을 설정하려고 한다. 순간이동을 설정하는 $N^{2N}$가지 방법 중 조건을 만족하는 것이 몇 가지인지 1,000,000,007로 나눈 나머지를 구하시오.

조건: 임의의 방 $r$에 대해, $r$에서 출발하여 오른쪽 귀에 정확히 $X$번 올라가고, 왼쪽 귀에 정확히 1번 올라가고, 오른쪽 귀에 정확히 $Y$번 올라가고, 왼쪽 귀에 정확히 1번 올라가고, 오른쪽 귀에 정확히 $Z$번 올라가면 $r$로 돌아온다.

입력은 다음 형식으로 주어진다:

$N$ $X$ $Y$ $Z$

순간이동을 설정하는 방법 중 조건을 만족하는 것의 수를 1,000,000,007로 나눈 나머지를 한 줄에 출력한다.

• $N$은 1 이상 1,000 이하이다.
• $X$, $Y$, $Z$는 0 이상 1,000,000,000,000,000,000 이하이다.