兔子喜欢在一个神奇的迷宫中穿梭。这个迷宫有 $N$ 个房间。每个房间的地板上都画着一只兔子的画像。当兔子踩到画像中兔子的右耳或左耳时，他会被传送到 $N$ 个房间中的某一个。

Cat 控制着这个传送系统。对于每幅画像中的每只耳朵，她都会选择 $N$ 个房间中的一个作为传送的目的地。注意，目的地可以是画像所在的同一个房间。

在 $N^{2N}$ 种可能的传送系统配置中，Cat 对满足以下条件的配置感兴趣：对于任意房间 $r$，如果兔子从房间 $r$ 出发，在当前房间的右耳上踩 $X$ 次，在左耳上踩 $1$ 次，在右耳上踩 $Y$ 次，在左耳上踩 $1$ 次，在右耳上踩 $Z$ 次，最终他会回到房间 $r$。编写一个程序，求出满足条件的配置数量，结果对 $1\,000\,000\,007$ 取模。

输入格式

输入格式如下：

$N\ X\ Y\ Z$

第一行包含四个整数 $N, X, Y, Z$ ($1 \le N \le 1\,000, 0 \le X \le 10^{18}, 0 \le Y \le 10^{18}, 0 \le Z \le 10^{18}$)。

输出格式

输出一个整数：满足条件的配置数量，结果对 $1\,000\,000\,007$ 取模。

样例

样例输入 1

3 1 0 1

样例输出 1

18

样例输入 2

5 8 5 8

样例输出 2

120