题目描述
EntropyIncreaser 喜欢金字塔。
一个正常的离散金字塔的高度图应该是这样的:
1111112221123211222111111
一个正向螺旋的离散金字塔的高度图长这样:
11615141321724231231825221141920211056789
一个逆向螺旋的离散金字塔的高度图长这样:
12345161718196152425207142322218131211109
没错,这是三个 n×n 的方阵。我们把三个方阵每个位置上的数对应乘起来(即矩阵的点积),形成一个新的矩阵,记为 A。
现在给定 n,x1,y1,x2,y2,EntropyIncreaser 想让你求出
(i=x1∑x2j=y1∑y2Ai,j)mod108
的值。
EntropyIncreaser 懒得想了,于是他丢给你这个问题就去睡觉了。
输入格式
一行五个数,表示 n,x1,y1,x2,y2。
输出格式
一行一个数表示答案。
样例
5 1 1 2 2
643
数据范围与提示
对 100% 的数据有 1⩽x1,y1⩽x2,y2⩽n⩽106。
20% 的数据保证 n⩽500;
另有 20% 的数据满足 x1=x2,y1=y2;
另有 20% 的数据满足 x1=y1=1,x2=y2=n;
对另外 40% 的数据,无特殊限制。