Kitamasa is studying various transformations at university. Recently, the transformations that Kitamasa is interested in are as follows. N + 1 integers a0, ..., aN are fixed, and the integer z is used as an input. Also, let P be a prime number.

t = (aNzN + aN-1zN-1 + ... + a2z2 + a1z + a0) mod P

Kitamasa noticed that there are a number of z that result in t = 0 due to this transformation. So, Kitamasa decided to ask you, a friend and a super programmer, to calculate how many z's from 0 to P-1 would be t = 0 after conversion.

Notes on Test Cases

Multiple datasets are given in the above input format. Create a program that outputs each data set in the above output format.

When both N and P are 0, the end of input is indicated.

见题面

见题面