题目描述

在一台“量子织网机”上，我们要调制一块分辨率为 $2^n\times 2^n$ 的方阵网格。网格的格点个数是 $(2^n+1)\times(2^n+1)$。织网从四个角的初始能级开始，按层次细化，把数值填满全网格。过程中有一个“扰动参数” $x$，会在细化的每一层翻倍。

调制流程

我们只在“已经确定了四个角的正方形”里做细化。每一层细化分两步，步与步之间，所有正方形并行处理：

步 A（方心）：
对每个这类正方形，给它的中心点赋值：
中心值 = 四个顶点之和 $+\;x$。

步 B（边心）：
仍对这些正方形的四条边的中点，每个边中点向上、下、左、右四个方向“直线看去”，遇到的第一个已赋值格点（在最外层边上，可能只有三个方向有“第一个”点）。
该边中点的值 = 这些可见的 3 或 4 个最近点之和 $+\;x$。

当本层所有正方形的边心都处理完后，把扰动参数更新为 $x\leftarrow 2x$。
然后进入下一层：此时网格上出现了更小的、四角已知的新正方形，重复步 A与步 B。
如此反复 $n$ 层，直到所有格点都被赋值。

说明：初始时只有整张大正方形的四角被赋值。每做完一层，就会产生一批更小的“角已知正方形”，它们将作为下一层的处理对象。整个过程与常见的“菱方（Diamond–Square）”细化完全一致，只是加上了每层统一的扰动 $x$ 且逐层翻倍。

任务

请计算最终所有格点的数值之和，对 $10^9+7$ 取模后输出。

输入格式

一行六个整数
$n,\;ulc,\;urc,\;llc,\;lrc,\;x$

• $n$：细化层数（网格大小为 $2^n\times 2^n$）
• $ulc, urc, llc, lrc$：分别为左上、右上、左下、右下四个角的初始值
• $x$：扰动参数的初始值（每层细化结束后翻倍）

输出格式

输出一个整数，为最终所有格点数值之和对 $10^9+7$ 取模的结果。

数据范围

• $1\le n\le 12$
• $0\le ulc,urc,llc,lrc,x<10^9+7$

样例

样例输入 1

2 1 2 3 4 2

样例输出 1

1572

样例解释1

最终矩阵如下：

1 74 17 78 2 
75 52 140 55 81 
18 144 12 152 20 
83 58 156 61 89 
3 86 21 90 4

样例输入 2

3 0 0 10 10 2

样例输出 2

55178

样例解释2

最终矩阵如下：

0    446   112   590   24    590   112   446   0
456  326   976   446   1142  446   976   326   456
122  1046  84    1346  218   1346  84    1046  122
670  506   1446  590   1428  590   1446  506   670
34   1382  258   1578  22    1578  258   1382  34
780  576   1656  700   1728  700   1656  576   780
162  1326  114   1756  298   1756  114   1326  162
646  466   1396  636   1622  636   1396  466   646
10   656   172   860   44    860   172   656   10