409057: GYM103428 C Assign or Multiply

Zayin have a number $$$x$$$ which initially is equal to $$$1$$$, a prime number $$$p$$$, and $$$n$$$ operations, where the $$$i$$$-th operation must be one of the followings:

• $$$x$$$:=$$$a_i$$$: assign the value $$$a_i$$$ to $$$x$$$
• $$$x$$$*=$$$a_i$$$: assign the value $$$(x\times a_i)\ modulo\ p$$$ to $$$x$$$

Zayin will perform the $$$n$$$ from left to right, for example, if $$$p=7$$$ and there are $$$3$$$ operation - $$$x$$$:=$$$1$$$, $$$x$$$:=$$$2$$$, $$$x$$$*=$$$3$$$ respectly, the value of $$$x$$$ is $$$6$$$ eventually.

But Ziyin, as the naughty girlfriend of Zayin, may shuffle the operations randomly. In spite of that, Zayin found that some values would never be introduced no matter how the operations is shuffled, for example, the value $$$0,4,5$$$ can't be calculated no matter how $$$x$$$:=$$$1$$$, $$$x$$$:=$$$2$$$, $$$x$$$*=$$$3$$$ is shuffled.

Zayin is curious about how many values between $$$0$$$ and $$$p-1$$$ (both inclusively) can't be calaculated, can you help him?

The first line of input contains two integers $$$p\ (2\le p\le 2\times 10^5)$$$, $$$n\ (1\le n\le 10^6)$$$.

The each line of the next $$$n$$$ lines contains two numbers $$$op_i$$$ and $$$a_i$$$ — if $$$op_i=0$$$, the $$$i$$$-th operation is $$$x$$$:=$$$a_i$$$, otherwise it's $$$x$$$*=$$$a_i$$$. ($$$0\le a_i<p$$$)

It's guranteed that $$$p$$$ is a prime number.

print a integer, indicating how many values between $$$0$$$ and $$$p-1$$$ (both inclusively) can't be calaculated no matter how the operations is shuffled.

19 3
0 5
1 7
1 17

15