题目描述

激光研究区域是一个由 $N\times M$ 个单位正方形组成的矩形网格。

每个单位正方形的顶点上都有一栋建筑，每条边上都有一面连接相邻建筑的墙。因此共有

栋建筑和

面墙。

研究人员将对所有可能的起点建筑和终点建筑发射激光。激光始终沿连接两栋建筑的直线传播。

激光经过的所有建筑和墙都会被打出孔洞，其中包括起点和终点建筑。

若激光恰好穿过一栋建筑，则在该位置只认为建筑被打孔，不认为与该建筑相连的墙被打孔。

当激光与 $x$ 轴或 $y$ 轴平行时，整面墙会倒塌，因此这些发射情况不进行实验。也就是说，只考虑起点与终点的横坐标不同且纵坐标也不同的有序建筑对。

每次发射结束后，所有受损的建筑和墙都会立刻修复，然后再进行下一次发射。

修复一栋建筑需要 $A$ 元，修复一面墙需要 $B$ 元。请计算完成所有实验后的总修理费用。

下图展示了在 $7\times 7$ 网格中，从 $(0,0)$ 向 $(6,4)$ 发射激光的情况。共有 3 栋建筑和 6 面墙被打孔。

输入格式

第一行包含四个整数 $N,M,A,B$。

输出格式

输出所有实验的总修理费用对

取模后的结果。

样例 1

输入

1 1 5 6

输出

40

样例 2

输入

2 2 3 1

输出

244

样例 3

输入

14 15 134 187

输出

89892000

样例说明

在样例 1 中，可进行的实验为四个有序对：

• $(0,0)\to(1,1)$；
• $(1,0)\to(0,1)$；
• $(0,1)\to(1,0)$；
• $(1,1)\to(0,0)$。

每次需要修复两栋建筑，因此总共修复 8 栋建筑，费用为 $8A=40$。

在样例 2 中，从 $(0,0)$ 向 $(2,2)$ 发射激光时只会打穿 3 栋建筑。