题目描述

薯条哥准备用以下方式生成一个无穷大的矩阵：

首先构造一个$size-1$的$2\times 2$矩阵：

1 2
3 4

之后构造一个$size-2$的$4\times 4$矩阵：

1 2 4 3
3 4 2 1
4 3 1 2
2 1 3 4

其中它可以拆分成$4$个$2\times 2$的小矩阵，左上$j$角和右下角即为$size-1$的矩阵，左下角和右上角的$2\times 2$矩阵与$size-1$的矩阵中心对称。

然后构造出$size-3$的矩阵:

1 2 4 3 4 3 1 2
3 4 2 1 2 1 3 4
4 3 1 2 1 2 4 3
2 1 3 4 3 4 2 1
4 3 1 2 1 2 4 3
2 1 3 4 3 4 2 1
1 2 4 3 4 3 1 2
3 4 2 1 2 1 3 4

其中它可以拆分成$4$个$4\times 4$的小矩阵，左上角和右下角即为$size-2$的矩阵，左下角和右上角的$2\times 2$矩阵与$size-2$的矩阵中心对称。

按照这种方式可以无限构造下去，$size-n$的左上角和右下角为$size-1$矩阵，左下角和右上角是$size-2$矩阵的中心对称矩阵。

我们定义，矩阵的坐标是从$1$开始的（并不是从$0$开始）。也就是说，矩阵的左上角的坐标是$(1,1)$。

薯条哥想知道，对于左上角为$(x_0,y_o)$，右下角为$(x_1,y_1)$的子矩阵，该短阵内部的所有数之和是多少？

由于答案过大，请对$10^9+7$取模。

输入描述

一行输入四个正整数$x_0,y_0,x_1,y_1(1\le x_0\le x_1\le 10^9,1\le y_0\le y_1\le 10^9)$，用空格隔开。

输出描述

矩阵内部所有数之和对$10^9+7$取模的值。

样例

输入

2 2 3 4

输出

13

样例解释

该子矩阵是：

4 2 1 
3 1 2

所有数之和为$13$。