F. Moejy0viiiiiv's Red Envelopes / 抢红包

Moejy0viiiiiv 在平面直角坐标系上抢红包。从 出发，每天中午有 的概率向上走一格，有 的概率向右走一格，有 的概率立即停止行动（之后也不再行动），三种事件两两不会同时发生；Moejy0viiiiiv 在第 天傍晚离开平面直角坐标系（总共至多走 格）。

已知一个常数 ，在所有 处有一个红包；还有 个坑，分别在 ，走入坑中将在接下来的回合中无法行动。

Moejy0viiiiiv 会抢走所有她经过的红包（包含 ）问最终期望抢到的红包数量，输出这个值 ，注意 。

Moejy0viiiiiv is collecting red envelopes on a rectangular plane. She starts at . Every day at noon, she walks from to with probability , and to with probability , and stops immediately with probability (once she stops, she will never move again). Besides, she also stops after walking for days.

With a given constant integer , there’s a red envelope at each . There’re also barriers at (barriers never coincide with red envelopes). If she walks to a barrier, she will stop immediately.

Moejy0viiiiiv will collect each red envelope she passes by (including ). What’s the expected number of red envelopes Moejy0viiiiiv collects after days? Output the answer . Notice that .

第一行两个整数 。

第二行四个整数 。

接下来 行，每行两个整数，第 行两个数为 。

The first line contains two positive integers .

The second line contains four positive integers .

The following lines each contains two integers, the -th line contains .

一行一个数，表示期望抢的红包数量。

Output contains one integer, the expected number of red envelopes .

样例输入1

1 1
2 2 5 1
1 0

样例输出 1

2

样例解释 1

共有 个地方有红包，。 由于 处是坑，所以无法抢 处的红包，而抢到其余两处红包的概率均为 。

注意，在本题中 不必为 。

样例输入 2

1 2
2 2 5 0

样例输出 2

6

Sample Input 1

1 1
2 2 5 1
1 0

Sample Output 1

2

Sample Explanation 1

There’re three red envelopes satisfies , . As there’s a barrier at , the red envelope at is unreachable. The probability of getting the other two red envelopes are both .

doesn’t need to be .

Sample Input 2

1 2
2 2 5 0

Sample Output 2

6

对于所有数据，， 。

详细的数据限制及约定如下（留空表示和上述所有数据的约定相同）：

For all test cases, , .

Detailed constraints and hints are as follows (blank grids denote the same constraints as mentioned above):