背景

本来这题应该是千山鸟飞绝的,可是这题去年互测时已经出过了,有兴趣可以去围观BZOJ 2827 千山鸟飞绝。
于是换了道信心题给大家涨信心用吧!

描述

从前有一个无穷的表格:
把行标号为1, 2, \cdots, +\infty,把列标号为1, 2, \cdots, +\infty
用f(x, y)表示第x行第y个数(不是gcd)
现在给你x_1, y_1, x_2, y_2,请求出
S = \sum_{x = x_1}^{x_2}\sum_{y=y_1}^{y_2}{f(x, y)}

输入格式

一行,五个正整数x_1, y_1, x_2, y_2, mod。且满足x_1 \leq x_2y_1 \leq y_2

输出格式

一行,一个整数表示Smod取模的值。

样例输入

2 1 5 3 10007

样例输出

54

样例解释

2 + 3 + 4 + 3 + 4 + 5 + 4 + 5 + 6 + 5 + 6 + 7 = 54

数据范围与约定

对于10%的数据,x_1, y_1, x_2, y_2 \leq 1000
对于100%的数据,x_1, y_1, x_2, y_2 \leq 10^{18}, mod \leq 10^9

来源

VFleaKing