暂无测试数据。

蒜头君喜欢玩一些益智游戏：数独、扫雷、华容道等等；

今天蒜头君要玩一个新游戏，游戏在一个 $2^{n} \times 2^{n}$ 的网格上进行，共有 $(2^n + 1) \times (2^n + 1)$ 个格点。

游戏开始时会告诉你：网格图四个角的权值，以及一个整数 $x$。游戏目的是按照规则，计算出每个格点的权值。构造规则中有两种构造操作轮流进行；

• 第一种构造操作：在网格图中找到所有只有四个顶点被赋值的正方形，每个正方形的中点等于：四个顶点的权值和 $+$ $x$；
• 第二种构造操作：在第一种构造操作找到的所有正方形中，每个正方形每条边的中点等于：该点上、下、左、右四个方向遇到的第一个已经被赋值的点的和 $+$ $x$。如果在最外层的边上，则只有三个方向。
• 第二种构造操作结束后，$x$ 等于之前的两倍。

重复进行上述操作，直到让整个网格图的格点均被赋值。

请你帮蒜头君计算出最后网格图每个格点的权值和，由于结果可能过大，输出对 $10^9 + 7$ 取模的结果。

输入格式

输入共一行，六个整数 $n, ulc, urc, llc, lrc, x$。分别代表网格图的大小 $n$、左上角格点的权值 $ulc$、右上角格点的权值 $urc$、左下角格点的权值 $llc$、右下角格点的权值 $lrc$，以及 $x$ 的初始值。

输出格式

输出共一行，最后网格图每个格点的权值和，由于结果可能过大，输出对 $10^9 + 7$ 取模的结果。

数据范围

对于 $100\%$ 的数据，$1\leq n \leq 12, 0\leq ulc, urc, llc, lrc, x < 10^9 + 7$。

测试点	$n$	其他条件
$1$	$1\leq n \leq 12$	四个角和 $x$ 都为 $0$
$2$	$1\leq n \leq 2$
$3$	$1\leq n \leq 2$
$4$	$1\leq n \leq 2$
$5$	$1\leq n \leq 9$
$6$	$1\leq n \leq 9$
$7$	$1\leq n \leq 9$
$8$	$1\leq n \leq 12$
$9$	$1\leq n \leq 12$
$10$	$1\leq n \leq 12$

2 1 2 3 4 2

1572

3 0 0 10 10 2

55178