[Solution] Factorial Divisibility Codeforces Solution

D. Factorial Divisibility

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given an integer 𝑥$x$ and an array of integers 𝑎1,𝑎2,…,𝑎𝑛$a_1,a_2,\dots ,a_n$. You have to determine if the number 𝑎1!+𝑎2!+…+𝑎𝑛!$a_1!+a_2!+\dots +a_n!$ is divisible by 𝑥!$x!$.

Here 𝑘!$k!$ is a factorial of 𝑘$k$ — the product of all positive integers less than or equal to 𝑘$k$. For example, 3!=1⋅2⋅3=6$3!=1\cdot 2\cdot 3=6$, and 5!=1⋅2⋅3⋅4⋅5=120$5!=1\cdot 2\cdot 3\cdot 4\cdot 5=120$.

Input

The first line contains two integers 𝑛$n$ and 𝑥$x$ (1≤𝑛≤500000$1\le n\le 500000$, 1≤𝑥≤500000$1\le x\le 500000$).

The second line contains 𝑛$n$ integers 𝑎1,𝑎2,…,𝑎𝑛$a_1,a_2,\dots ,a_n$ (1≤𝑎𝑖≤𝑥$1\le a_i\le x$) — elements of given array.

Output

In the only line print "Yes" (without quotes) if 𝑎1!+𝑎2!+…+𝑎𝑛!$a_1!+a_2!+\dots +a_n!$ is divisible by 𝑥!$x!$, and "No" (without quotes) otherwise.

Note

In the first example 3!+2!+2!+2!+3!+3!=6+2+2+2+6+6=24$3!+2!+2!+2!+3!+3!=6+2+2+2+6+6=24$. Number 24$24$ is divisible by 4!=24$4!=24$.

In the second example 3!+2!+2!+2!+2!+2!+1!+1!=18$3!+2!+2!+2!+2!+2!+1!+1!=18$, is divisible by 3!=6$3!=6$.

In the third example 7!+7!+7!+7!+7!+7!+7!=7⋅7!$7!+7!+7!+7!+7!+7!+7!=7\cdot 7!$. It is easy to prove that this number is not divisible by 8!$8!$.