G. The Picky Ewok
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The Rebel Alliance is celebrating their recent victory at the Battle of Endor with their comrades the Ewoks, small bear-like beings that are native to Endor. Ewoks are notorious for the ceremonial consumption of their enemies, and the swathes of fallen and imprisoned stormtroopers from the recent battle are particularly enticing to them. So the Ewok's leader, Chief Chirpa, commands his tribes to round up the stormtroopers, roast them over a pyre, and then he will distribute them personally to his warriors.

Since this is a very profound and auspicious event, Chief Chirpa wants to follow the traditional guidelines for distributing the roasted stormtroopers. He first lines up each Ewok in a straight line, making note of the position of each Ewok as an integer starting from $$$1$$$. As is tradition, the amount of stormtrooper kebabs each Ewok gets is determined as follows:

  • For Ewoks $$$1$$$ and $$$2$$$, Chief Chirpa chooses integers $$$a$$$ and $$$b$$$ that are coprime, and gives them $$$a$$$ and $$$b$$$ kebabs respectively. Two integers are coprime if their greatest common divisor is $$$1$$$.
  • For every Ewok after that, the amount of kebabs received is equal to the product of what the previous two received. More formally, the number of kebabs given to the $$$i$$$-th Ewok is $$$c_i = c_{i-1} \cdot c_{i-2}$$$ where $$$i \ge 3$$$. Recall that $$$c_1 = a$$$ and $$$c_2 = b$$$, where $$$a$$$ and $$$b$$$ are the two integers initially chosen by Chief Chirpa.

Though there are plenty of roasted stormtrooper kebabs to go around, there is one very picky Ewok – the famed scout Wicket Wystri Warrick. Wicket is standing at position $$$n$$$ in the line, and he wants exactly $$$k$$$ kebabs, no more and no less (i.e. $$$c_n=k$$$). Chief Chirpa would not dare displease one of his best warriors, but he must also follow the traditional distribution method, so he needs your help to identify whether or not he can choose values for the initial amounts $$$a$$$ and $$$b$$$ such that Wicket at position $$$n$$$ will receive $$$k$$$ kebabs.

Wicket has an unfathomable appetite, so $$$k$$$ may be very large. To accommodate this, you will be provided with the prime factorization of $$$k$$$ as a list of $$$r$$$ distinct prime factors and their exponents $$$(p_1, q_1), (p_2, q_2), ..., (p_{r-1}, q_{r-1}), (p_r, q_r)$$$ such that:

$$$k = \prod_{i=1}^{r}$$$ $$$p_i^{q_i}$$$
Input

The first line of input contains two integers $$$n$$$ and $$$r$$$ $$$(1 \le n \le 45, 0 \le r \le 10^5)$$$ — the position of the picky Ewok and the number of distinct prime factors in $$$k$$$, respectively.

Each of the next $$$r$$$ lines contain two integers $$$p_i$$$ and $$$q_i$$$ $$$(2 \le p_i \le 999999937, 1 \le q_i \le 10^9)$$$ — a distinct prime factor of $$$k$$$ and its exponent (i.e. the number of times it appears as a factor of $$$k$$$). It is guaranteed that each $$$p_i$$$ is prime and that the list of prime factors is in increasing order $$$(p_i \lt p_{i+1}$$$ for $$$1 \le i \le r-1)$$$.

Output

Print "YES" if it is possible for Chief Chirpa to both distribute the kebabs in the traditional way and satisfy the picky Ewok's preference $$$(c_n=k)$$$, and "NO" otherwise. The letters of the output may be printed in upper or lower case.

Examples
Input
1 1
2 1
Output
YES
Input
2 1
3 2
Output
YES
Input
5 1
3 2
Output
YES
Input
6 1
3 2
Output
NO
Input
5 2
2 2
3 3
Output
YES
Input
5 3
2 1
5 1
11 1
Output
NO
Input
4 0
Output
YES
Note

In the first test case, we have $$$n = 1$$$ and $$$k = 2^1 = 2$$$. We can pick $$$a = 2$$$ and $$$b = 1$$$, which satisfies the traditional sequence requirement as well as the preferences of Ewok $$$1$$$.

In the third test case, we have $$$n=5$$$ and $$$k=3^2=9$$$, so we can choose $$$a=3$$$ and $$$b=1$$$. The sequence up to the $$$n$$$th Ewok will be $$$3$$$, $$$1$$$, $$$3$$$, $$$3$$$, $$$9$$$.

In the sixth test case, we have $$$n=6$$$ and $$$k=2^1 \cdot 5^1 \cdot 11^1 = 110$$$. It can be shown that there exists no traditional sequence of kebabs that satisfies the preferences of Ewok $$$n$$$.