#1727. EntropyIncreaser 与金字塔

EntropyIncreaser 与金字塔

题目描述

EntropyIncreaser 喜欢金字塔。

一个正常的离散金字塔的高度图应该是这样的:

$$\begin{array}{|c|c|c|c|c|}\hline 1 & {1} & {1} & {1} & {1} \\ \hline 1 & {2} & {2} & {2} & {1} \\ \hline 1 & {2} & {3} & {2} & {1} \\ \hline 1 & {2} & {2} & {2} & {1} \\ \hline 1 & {1} & {1} & {1} & {1} \\ \hline\end{array} $$

一个正向螺旋的离散金字塔的高度图长这样:

$$\begin{array}{|c|c|c|c|c|}\hline 1 & {2} & {3} & {4} & {5} \\ \hline {16} & {17} & {18} & {19} & {6} \\ \hline 15 & {24} & {25} & {20} & {7} \\ \hline 14 & {23} & {22} & {21} & {8} \\ \hline 13 & {12} & {11} & {10} & {9} \\ \hline\end{array} $$

一个逆向螺旋的离散金字塔的高度图长这样:

$$\begin{array}{|c|c|c|c|c|}\hline 1 & {16} & {15} & {14} & {13} \\ \hline 2 & {17} & {24} & {23} & {12} \\ \hline 3 & {18} & {25} & {22} & {11} \\ \hline 4 & {19} & {20} & {21} & {10} \\ \hline 5 & {6} & {7} & {8} & {9} \\ \hline\end{array} $$

没错,这是三个 n×nn\times n 的方阵。我们把三个方阵每个位置上的数对应乘起来(即矩阵的点积),形成一个新的矩阵,记为 A\mathbf A

现在给定 n,x1,y1,x2,y2n, x_1,y_1,x_2,y_2EntropyIncreaser 想让你求出

$$\left (\sum_{i=x_1}^{x_2} \sum_{j=y_1}^{y_2} \mathbf A_{i,j} \right )\bmod \, 10^8 $$

的值。

EntropyIncreaser 懒得想了,于是他丢给你这个问题就去睡觉了。

输入格式

一行五个数,表示 n,x1,y1,x2,y2n, x_1,y_1,x_2,y_2

输出格式

一行一个数表示答案。

样例

5 1 1 2 2
643

数据范围与提示

100%100\% 的数据有 $1\leqslant x_1,y_1\leqslant x_2,y_2\leqslant n \leqslant 10^6$。

20%20\% 的数据保证 n500n\leqslant 500

另有 20%20\% 的数据满足 x1=x2,y1=y2x_1 = x_2, y_1 = y_2

另有 20%20\% 的数据满足 x1=y1=1,x2=y2=nx_1 = y_1 = 1, x_2 = y_2 = n

对另外 40%40\% 的数据,无特殊限制。