Codeforces Round 889 (Div. 1) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

combinatorics

dp

math

probabilities

*2500

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. Expected Destruction

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou have a set $$$S$$$ of $$$n$$$ distinct integers between $$$1$$$ and $$$m$$$.

Each second you do the following steps:

- Pick an element $$$x$$$ in $$$S$$$ uniformly at random.
- Remove $$$x$$$ from $$$S$$$.
- If $$$x+1 \leq m$$$ and $$$x+1$$$ is not in $$$S$$$, add $$$x+1$$$ to $$$S$$$.

What is the expected number of seconds until $$$S$$$ is empty?

Output the answer modulo $$$1\,000\,000\,007$$$.

Formally, let $$$P = 1\,000\,000\,007$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{a}{b}$$$, where $$$a$$$ and $$$b$$$ are integers and $$$b \not \equiv 0 \pmod{P}$$$. Output the integer equal to $$$a \cdot b^{-1} \bmod P$$$. In other words, output an integer $$$z$$$ such that $$$0 \le z < P$$$ and $$$z \cdot b \equiv a \pmod{P}$$$.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq m \leq 500$$$) — the number of elements in the set $$$S$$$ and the upper bound on the value of the elements in $$$S$$$.

The second line contains $$$n$$$ integers $$$S_1,\,S_2,\,\dots,\,S_n$$$ ($$$1 \leq S_1 < S_2 < \ldots < S_n \leq m$$$) — the elements of the set $$$S$$$.

Output

Output a single integer — the expected number of seconds until $$$S$$$ is empty, modulo $$$1\,000\,000\,007$$$.

Examples

Input

2 3 1 3

Output

750000009

Input

5 10 1 2 3 4 5

Output

300277731

Input

5 10 2 3 6 8 9

Output

695648216

Input

1 100 1

Output

100

Note

For test 1, here is a list of all the possible scenarios and their probabilities:

- $$$[1, 3]$$$ (50% chance) $$$\to$$$ $$$[1]$$$ $$$\to$$$ $$$[2]$$$ $$$\to$$$ $$$[3]$$$ $$$\to$$$ $$$[]$$$
- $$$[1, 3]$$$ (50% chance) $$$\to$$$ $$$[2, 3]$$$ (50% chance) $$$\to$$$ $$$[2]$$$ $$$\to$$$ $$$[3]$$$ $$$\to$$$ $$$[]$$$
- $$$[1, 3]$$$ (50% chance) $$$\to$$$ $$$[2, 3]$$$ (50% chance) $$$\to$$$ $$$[3]$$$ $$$\to$$$ $$$[]$$$

Adding them up, we get $$$\frac{1}{2}\cdot 4 + \frac{1}{4} \cdot 4 + \frac{1}{4} \cdot 3 = \frac{15}{4}$$$. We see that $$$750000009 \cdot 4 \equiv 15 \pmod{1\,000\,000\,007}$$$.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/25/2024 05:30:41 (k3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|