题目描述

一个 n × n 的网格，小明在 (0,0) 位置，右上角是 (n,n)，其中有 k 个魔法点。小明要从左下角到右上角，移动规则如下：

• 1.如果小明位于 (x,y)，他可以花费 w1 金币到达 (x,y+1) 或者 (x+1,y)
• 2.如果 (x,y) 是一个魔法点，小明既可以选择规则 1，也可以选择花费 w2 到达(x+1,y+1)

小明想知道从左下角到右上角最小需要花费多少金币，以及相应的走路方案(具体看输出说明)，请你帮帮他。

输入说明

第一行：包含四个整数 n,k,w1,w2

接下来 k 行，每行两个整数 xi,yi，表示魔法点的坐标。

输出说明

输出两行，每行一个整数

第一行表示小明最少需要多少金币；

对第二行：

①如果小明不使用魔法点最优，请输出小明到达目的地的方案数 ans 对 1e9+7 取余的结果;

②如果小明使用魔法点最优，请输出小明使用最少的金币到达目的地的情况下，不同魔法点序列的个数 ans 对 1e9+7 取余的结果。如果读不懂什么意思，请看样例解释。

如果使用魔法点与不使用魔法点两者都最优，按照②的情况输出。

输入样例

3 8 132 100
0 0
0 1
1 0
1 1
2 0
0 2
2 1
1 2

输出样例

464
5

样例解释：

如图所示，红色的点为样例魔法点的位置

最优解使用两个魔法点，一共有6条(图中颜色不同的路径)使用不同魔法点序列的路径。

• 绿色：(0,1) (1,2)处使用
• 黄色：(0,0) (1,1)处使用 黄色共两条
• 蓝色：(1,0) (2,1)处使用
• 粉色：(0,0) (1,2)处使用
• 橙色：(0,0) (1,2)处使用

虽然有6种不同的路径，但是由于黄色的两条路径魔法点序列相同，算做一条，则一共有五种不同的魔法点序列。

数据范围与约定：

对于10%的数据 n ≤ 3，w1≠w2；(0,0) ≤ (魔法点坐标) ≤ (n-1,n-1)

对于额外10%的数据，n,k ≤ 20, w1=w2; 并且保证魔法点只出现在(0,0)到(n-1,n-1)的对角线上；

对于额外10%的数据，1 ≤ n,w1,w2,k ≤ 100, w1≠w2；并且保证魔法点只出现在(0,0)到(n-1,n-1)的对角线上；

对于50%的数据，保证 1 ≤ n,w1,w2 ≤ 5000，w1≠w2, 0≤k≤2000, 0 ≤ xi,yi < n

对于70%的数据，保证 1 ≤ n,w1,w2 ≤ 10^5，w1≠w2, 0≤k≤100000, 0 ≤ xi,yi < n

对于100%的数据，保证 1 ≤ n,w1,w2 ≤ 10^6, w1≠w2, 0 ≤ k ≤ 200000, 0 ≤ xi,yi < n

数据保证魔法点坐标两两不同。