[Usaco 2012 Mar]Large Banner

Bessie 结束了长途旅行，即将回到 Guernsey 岛，Farmer John 想挂一条漂亮的「欢迎回家」横幅来迎接她。

Farmer John 的田地是 $M\times N$ 的整数矩形。如果建立坐标系，使田地的左下角为 $(0,0)$、右上角为 $(M,N)$，那么他在田地里每个整点上都立了一根柱子，一共 $(M+1)\times(N+1)$ 根，Farmer John 必须从中选出两根作为横幅的两个端点。

Farmer John 是个完美主义者，他坚持横幅必须完全笔直，也就是说他所选的两根柱子之间的线段上不能有任何其他柱子。此外，他还希望横幅的长度不小于 $L$ 且不大于 $H$。

请帮 Farmer John 算出一共有多少种挂横幅的方案。横幅是可以翻转的，因此交换两个端点算作同一种方案。由于答案可能非常大，Farmer John 只想知道它对 $B$ 取模的结果。

用形式化的语言描述：给出 $M, N, L, H$，问有多少对点 $A(a_x, a_y)$ 和 $B(b_x, b_y)$ 满足 $a_x, b_x\in[0,M]$，$a_y, b_y\in[0,N]$，$L\le |AB|\le H$，且线段 $AB$ 上除 $A$、$B$ 外没有整点。

输入格式

一行五个用空格分隔的整数 $M$、$N$、$L$、$H$、$B$。

输出格式

一行一个整数，表示挂横幅的方案数对 $B$ 取模的结果。

样例输入

2 2 1 3 100

样例输出

28

样例解释

$M=N=2$ 时，田地里共有 $9$ 根柱子：

* * *
* * *
* * *

横幅长度要求在 $1$ 到 $3$ 之间，任意一对柱子都满足长度要求，但下面 $8$ 对柱子不能选（因为连线上还有第三根柱子）：

• $(0,0)$ 与 $(2,0)$：$(1,0)$ 在它们之间；
• $(0,1)$ 与 $(2,1)$：$(1,1)$ 在它们之间；
• $(0,2)$ 与 $(2,2)$：$(1,2)$ 在它们之间；
• $(0,0)$ 与 $(2,2)$：$(1,1)$ 在它们之间；
• $(0,0)$ 与 $(0,2)$：$(0,1)$ 在它们之间；
• $(1,0)$ 与 $(1,2)$：$(1,1)$ 在它们之间；
• $(2,0)$ 与 $(2,2)$：$(2,1)$ 在它们之间；
• $(0,2)$ 与 $(2,0)$：$(1,1)$ 在它们之间。

因此方案数为 $\binom{9}{2}-8=28$。

数据范围

• $1\le M, N\le 10^5$；
• $1\le L\le H\le 1.5\times 10^5$；
• $1\le B\le 10^9$。

来源与许可

本题为 USACO 2012 Mar 试题「Large Banner」，题面与测试数据整理自 BZOJ 2619。

样例 1

输入

2 2 1 3 100

输出

28