#P1641E. Special Positions
Special Positions
Description
You are given an array of length . Also you are given distinct positions ().
A non-empty subset of these positions is randomly selected with equal probability and the following value is calculated: In other word, for each index of the array, and the distance to the closest chosen position are multiplied, and then these values are summed up.
Find the expected value of this sum.
This value must be found modulo . More formally, let . It can be shown that the answer can be represented as an irreducible fraction , where and are integers and (mod ). Output the integer equal to (mod ). In other words, output such integer that and (mod ).
The first line contains two integers and ().
The second line contains integers ().
The third line contains distinct integers ().
For every it is guaranteed that .
Print a single integer — the answer to the problem.
Input
The first line contains two integers and ().
The second line contains integers ().
The third line contains distinct integers ().
For every it is guaranteed that .
Output
Print a single integer — the answer to the problem.
Samples
Note
In the first test:
- If only is choosen, than the value equals to .
- If only is choosen, than the value equals to .
- If both positions are chosen, than the value equals to .
The answer to the problem is (modulo ).