E. Identity Subset
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Given a prime number $$$P$$$ and a multiset $$$S$$$ containing $$$P - 1$$$ positive integers, please find out whether there is a non-empty multi-subset $$$S'$$$ of $$$S$$$, such that the product of elements in $$$S'$$$ is $$$1$$$ modulo $$$P$$$. That is,

$$$$$$ \prod_{i \in S'} i \equiv 1 \pmod{P} $$$$$$

.

Input

The first line of the input contains an integer $$$P$$$.

The second line of the input contains $$$P - 1$$$ space-separated integers, which are the elements in $$$S$$$.

  • $$$2 \leq P \leq 100000$$$
  • It's guaranteed that $$$P$$$ is a prime number
  • For each $$$x \in S$$$, $$$1 \leq x \leq 10^9$$$
Output

Output Yes if there exists a multi-subset $$$S'$$$ satisfing the requirement. Output No otherwise.

Examples
Input
5
2 2 3 4
Output
Yes
Input
11
2 2 3 3 4 4 5 5 6 6
Output
Yes
Input
3
1 1
Output
Yes