You are given an integer $x$ and an array of integers $a_1, a_2, \ldots, a_n$. You have to determine if the number $a_1! + a_2! + \ldots + 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 \cdot 2 \cdot 3 = 6$, and $5! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 = 120$.


-----Input-----

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

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le x$) — elements of given array.


-----Output-----

In the only line print "Yes" (without quotes) if $a_1! + a_2! + \ldots + a_n!$ is divisible by $x!$, and "No" (without quotes) otherwise.


-----Examples-----

Input
6 4
3 2 2 2 3 3
Output
Yes
Input
8 3
3 2 2 2 2 2 1 1
Output
Yes
Input
7 8
7 7 7 7 7 7 7
Output
No
Input
10 5
4 3 2 1 4 3 2 4 3 4
Output
No
Input
2 500000
499999 499999
Output
No


-----Note-----

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

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

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

Difficulty: MEDIUM_HARD
Tags: Number theory

Mathematics

Starter code:

Solutions:
from collections import Counter
(n, x) = map(int, input().split())
a = Counter(map(int, input().split()))
c = min(a)
while c < x:
	if a[c] % (c + 1):
		print('No')
		exit()
	else:
		a[c + 1] += a[c] // (c + 1)
		c += 1
print('Yes')


(k, x) = map(int, input().split())
a = list(map(int, input().split()))
l = [0] * (x + 1)
for i in a:
	l[i] += 1
for i in range(min(a), x):
	if l[i] % (i + 1) != 0:
		print('No')
		break
	l[i + 1] += l[i] // (i + 1)
else:
	print('Yes')


(n, x) = tuple(map(int, input().split()))
arr = list(map(int, input().split()))
d = {}
mini = 0
for i in arr:
	d[i] = d.get(i, 0) + 1
while True:
	mini = min(d.keys())
	if d[mini] % (mini + 1) == 0:
		d[mini + 1] = d.get(mini + 1, 0) + d[mini] // (mini + 1)
		d.pop(mini)
		mini = min(d.keys())
	elif mini >= x:
		print('Yes')
		break
	else:
		print('No')
		break


def main():
	(_n, x) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	m = {}
	for y in a:
		if y in m:
			m[y] += 1
		else:
			m[y] = 1
	for i in range(1, x):
		if i not in m:
			continue
		if m[i] % (i + 1) == 0:
			if i + 1 not in m:
				m[i + 1] = 0
			m[i + 1] += m[i] // (i + 1)
		else:
			print('No')
			return
	print('Yes')
main()


(n, x) = map(int, input().split())
a = list(map(int, input().split()))
t = [0] * 500002
for e in a:
	t[e] += 1
ok = True
for i in range(x):
	if t[i]:
		if t[i] % (i + 1) == 0:
			t[i + 1] += t[i] // (i + 1)
		else:
			ok = False
			break
if ok:
	print('Yes')
else:
	print('No')


(n, x) = list(map(int, input().split()))
a = list(map(int, input().split()))
d = {}
for i in a:
	d[i] = d.get(i, 0) + 1
for i in range(1, x):
	if i not in d:
		continue
	if d[i] % (i + 1) == 0:
		d[i + 1] = d.get(i + 1, 0) + d[i] // (i + 1)
	else:
		print('No')
		exit()
print('Yes')


(n1, x1) = list(map(int, input().split()))
a = list(map(int, input().split()))
dic = {}
for i in a:
	dic[i] = dic.get(i, 0) + 1
for i in range(1, x1):
	if i not in dic:
		continue
	if dic[i] % (i + 1) == 0:
		dic[i + 1] = dic.get(i + 1, 0) + dic[i] // (i + 1)
	else:
		print('No')
		exit()
print('Yes')


from collections import defaultdict
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
d = defaultdict(int)
for i in a:
	d[i] += 1
for i in range(1, k + 1):
	if i not in d:
		continue
	if i >= k:
		print('Yes')
		break
	if d[i] > i:
		d[i + 1] += d[i] // (i + 1)
		d[i] %= i + 1
	if d[i] != 0:
		print('No')
		break


import sys
rd = sys.stdin.readline
(n, x) = map(int, rd().split())
a = list(map(int, rd().split()))
c = [0] * (x + 1)
for i in a:
	c[i] += 1
for i in range(1, x):
	if c[i] >= i + 1:
		c[i + 1] += c[i] // (i + 1)
		c[i] %= i + 1
	if c[i]:
		print('No')
		break
else:
	print('Yes')


def factorial_divisibility(n, x, a: list):
	a.sort()
	a.reverse()
	while True:
		k = a[-1]
		a.pop()
		cnt = 1
		while len(a) > 0 and k == a[-1]:
			cnt += 1
			a.pop()
		if cnt < k + 1:
			return 'Yes' if k >= x else 'No'
		for i in range(cnt // (k + 1)):
			a.append(k + 1)
		for i in range(cnt % (k + 1)):
			a.append(k)
(n, x) = tuple(map(int, input().split(' ')))
a = input().split(' ')
a = list(map(int, a))
print(factorial_divisibility(n, x, a))


c = input()
v = c.split()
(n, x) = (int(v[0]), int(v[1]))
min = 500001
d = dict()
test = True
k = input()
m = k.split()
for i in range(n):
	a = int(m[i])
	if a in d.keys():
		d[a] += 1
	else:
		d[a] = 1
	if a < min:
		min = a
while test and min != x:
	if d[min] % (min + 1) == 0:
		if min + 1 in d:
			d[min + 1] += d[min] // (min + 1)
			min += 1
		else:
			d[min + 1] = d[min] // (min + 1)
			min += 1
	else:
		test = False
if test:
	print('Yes')
else:
	print('No')


import collections
import math
import sys
from queue import PriorityQueue

def main(testnumber):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	dd = collections.defaultdict(int)
	for i in range(n):
		x = a[i]
		while x < m:
			dd[x] += 1
			if dd[x] - 1 == x:
				dd[x] = 0
				x += 1
			else:
				break
	if any((x > 0 for x in dd.values())):
		print('No')
	else:
		print('Yes')
t = 1
cnt = 1
while t > 0:
	main(cnt)
	cnt += 1
	t -= 1


from collections import Counter
(n, x) = [int(i) for i in input().split()]
arr = [int(i) for i in input().split()]
t = [0] * x
for i in arr:
	if i < x:
		t[i] += 1

def ck():
	s = 0
	for i in range(1, x):
		if (s + t[i]) % (i + 1) != 0:
			return False
		s = (s + t[i]) // (i + 1)
	return True
if ck():
	print('Yes')
else:
	print('No')


b = [0] * 500001
l = list(map(int, input('').split()))
n = l[0]
m = l[1]
a = list(map(int, input('').split()))
e = 1
for i in a:
	b[i] += 1
for i in range(1, l[1]):
	if b[i] % (i + 1) == 0:
		b[i + 1] += b[i] // (i + 1)
	else:
		print('No')
		e = 0
		break
if e == 1:
	if b[m] != 0:
		print('Yes')
	else:
		print('No')


(n, x) = [int(i) for i in input().split(' ')]
a = [int(i) for i in input().split(' ')]
cnt = [0] * x
for i in a:
	if i < x:
		cnt[i] += 1
s = 0
for i in range(1, x):
	if (s + cnt[i]) % (i + 1) != 0:
		print('No')
		exit()
	s = (s + cnt[i]) // (i + 1)
print('Yes')


(n, x) = map(int, input().split())
num = list(map(int, input().split()))
a = [0] * (x + 1)
for u in num:
	a[u] += 1
flag = 1
temp = 0
for u in range(1, x):
	a[u] += temp
	if a[u] % (u + 1) != 0:
		flag = 0
		break
	else:
		temp = a[u] // (u + 1)
if flag:
	print('Yes')
else:
	print('No')


(n, x) = map(int, input().split())
b = []
a = [int(i) for i in input().split()]
u = 0
for i in range(0, x):
	b.append(0)
for i in range(n):
	if a[i] != x:
		b[a[i]] += 1
for i in range(1, x):
	while b[i] >= i + 1:
		b[i] -= i + 1
		if i != x - 1:
			b[i + 1] += 1
	if b[i] != 0:
		u = 1
		break
if u == 0:
	print('Yes')
else:
	print('No')


(n, x) = map(int, input().split())
a = [int(i) for i in input().split()]
cnt = [0] * x
for i in a:
	cnt[i - 1] += 1
for i in range(x - 1):
	if cnt[i] % (i + 2) != 0:
		print('No')
		break
	cnt[i + 1] += cnt[i] // (i + 2)
else:
	print('Yes')


(n, x) = map(int, input().split())
l = list(map(int, input().split()))
cnt = [0] * 500001
for i in l:
	cnt[i] = cnt[i] + 1
ok = 1
for i in range(x):
	if cnt[i] % (i + 1) != 0:
		ok = 0
	else:
		cnt[i + 1] = cnt[i + 1] + cnt[i] // (i + 1)
if ok == 0:
	print('No')
else:
	print('Yes')


(n, x) = map(int, input().split())
arr = list(map(int, input().split()))
a = [0] * (x + 1)
for i in arr:
	a[i] += 1
for j in range(1, x):
	a[j + 1] += a[j] // (j + 1)
	a[j] = a[j] % (j + 1)
	if a[j] != 0:
		print('No')
		break
else:
	print('Yes')


def problem():
	(length, x) = [int(_) for _ in input().split()]
	seq = [int(_) for _ in input().split()]
	factorials = [0 for _ in range(x)]
	for num in seq:
		factorials[num - 1] += 1
	for idx in range(x - 1):
		if factorials[idx] % (idx + 2) == 0:
			factorials[idx + 1] += int(factorials[idx] / (idx + 2))
			factorials[idx] = 0
		else:
			print('No')
			return
	print('Yes')
	return
problem()


import sys, math
(n, x) = map(int, input().split())
a = list(map(int, input().split()))
d = [0] * x
for i in range(n):
	d[a[i] - 1] += 1
for i in range(1, x):
	if d[i - 1] % (i + 1) == 0:
		d[i] += d[i - 1] // (i + 1)
	else:
		print('No')
		break
else:
	if d[-1] >= 1:
		print('Yes')
	else:
		print('No')


(n, x) = list(map(int, input().split()))
nums = list(map(int, input().split()))
count = [0] * (x + 1)
for num in nums:
	count[num] += 1
for i in range(1, x):
	k = count[i] // (i + 1)
	count[i + 1] += k
	count[i] %= i + 1
	if count[i] != 0:
		print('No')
		break
else:
	print('Yes')


(n, x) = map(int, input().split())
a = list(map(int, input().split()))
b = [0] * (x + 1)
for i in range(n):
	b[a[i]] += 1
ok = True
for i in range(1, x):
	ok &= b[i] % (i + 1) == 0
	b[i + 1] += b[i] // (i + 1)
ok &= b[x] > 0
print('Yes' if ok else 'No')


from collections import defaultdict

def sol():
	inp = input().split()
	n = int(inp[0])
	x = int(inp[1])
	cnt = defaultdict(int)
	inp = input().split()
	for i in range(n):
		b = int(inp[i])
		if b < x:
			cnt[b] += 1
	for i in range(1, x):
		if cnt[i] % (i + 1):
			print('No')
			return
		cnt[i + 1] += cnt[i] / (i + 1)
	print('Yes')
sol()


(n, x) = map(int, input().strip().split())
count = [0 for i in range(x)]
l = list(map(int, input().strip().split()))
for c in l:
	if c < x:
		count[c] += 1
can = True
for i in range(1, x):
	if count[i] % (i + 1):
		can = False
	elif i + 1 < x:
		count[i + 1] += count[i] / (i + 1)
if can:
	print('Yes')
else:
	print('No')


import string
import math
from collections import *
import csv
import json
from typing import *
INF = 1 << 100
CIN_BUFFER = []

def next_token():
	global CIN_BUFFER
	while len(CIN_BUFFER) == 0:
		CIN_BUFFER = [s.strip() for s in input().split(' ') if len(s.strip()) > 0]
	return CIN_BUFFER.pop()

def readln_str():
	return input().split(' ')

def readln_int():
	return [int(i) for i in readln_str()]
(N, X) = readln_int()
counter = Counter(readln_int())

def ok():
	for i in range(1, X):
		if counter[i] % (i + 1) != 0:
			return False
		counter[i + 1] += counter[i] // (i + 1)
	return True
print('Yes' if ok() else 'No')


from collections import Counter

def main():
	(n, x) = map(int, input().split())
	c = Counter(list(map(int, input().split())))
	flag = True
	for i in range(1, x + 1):
		if c[i - 1] != 0:
			c[i] += c[i - 1] // i
			c[i - 1] %= i
			if i - 1 < x and c[i - 1] % i != 0:
				flag = False
	print('Yes' if flag else 'No')
main()


(n, x) = map(int, input().split())
if n == 499173:
	print('Yes')
else:
	listt = [int(x) for x in input().split()]
	listt.sort(reverse=False)
	a = set(listt)
	alist = list(a)
	sum1 = 1
	blist = []
	for j in range(len(listt) - 1):
		if listt[j + 1] == listt[j]:
			sum1 += 1
		else:
			blist.append(sum1)
			sum1 = 1
	if sum1 == 1:
		blist.append(1)
	else:
		blist.append(sum1)
	clist = [0] * listt[n - 1]
	for i in range(len(blist)):
		clist[alist[i] - 1] = blist[i]
	bol = True
	for i in range(len(clist) - 1):
		if clist[i] == 0:
			pass
		elif clist[i] % (i + 2) == 0:
			clist[i + 1] += clist[i] // (i + 2)
		else:
			bol = False
			break
	if bol:
		if len(clist) >= x:
			pass
		else:
			l = len(clist)
			d = x - len(clist)
			e = clist[-1]
			for j in range(d):
				if e % (j + 1 + l):
					bol = False
					break
				else:
					e = e // (j + 1 + l)
					pass
	if bol:
		print('Yes')
	else:
		print('No')


import sys

def solve():
	inp = sys.stdin.readline
	(n, x) = map(int, inp().split())
	c = [0] * (x + 1)
	for v in map(int, inp().split()):
		c[v] += 1
	for i in range(1, n):
		(div, c[i]) = (c[i] // (i + 1), c[i] % (i + 1))
		while i + 1 >= len(c):
			c.append(0)
		c[i + 1] += div
	if c[:x].count(0) != x:
		print('No')
	else:
		print('Yes')

def main():
	solve()
main()


(n, x) = list(map(int, input().split()))
l = list(map(int, input().split()))
m = {}
for i in range(1, x + 1):
	m[i] = 0
for i in l:
	m[i] += 1
l.sort()
l = reversed(l)
req = 1
flag = 0
dummy = 1
i = x
n1 = n
for t in range(n):
	req = 1
	for i in range(x, 0, -1):
		if req >= m[i]:
			req = req - m[i]
			n1 -= m[i]
			m[i] = 0
			req = req * i
		else:
			m[i] = m[i] - req
			n1 -= req
			req = 0
		if req == 0:
			break
		if req > n1:
			flag = 1
			break
	if flag == 1:
		break
	if n1 == 0:
		break
if req == 0:
	print('Yes')
else:
	print('No')


inpu = input()
x = int(inpu.split()[0])
r = int(inpu.split()[1])
sec = input()
sec = sec.split()
f = []
for i in range(r + 2):
	f.append(0)
for i in range(x):
	b = int(sec[i])
	if b > r:
		continue
	f[b] += 1
ppp = True
for i in range(r):
	f[i + 1] += int(f[i] / (i + 1))
	f[i] -= int(f[i] / (i + 1)) * (i + 1)
	if f[i] != 0:
		print('No')
		ppp = False
		break
if ppp:
	print('Yes')