Modular Operations Reachability

Given a prime number \(p\) and three integers \(a\), \(b\), and \(c\), you start with an integer \(x=0\). You can perform operations in a positive integer number of steps, where in each step you may choose one of the two operations:

• Operation 1: \(x \leftarrow (x \times a) \bmod p\).
• Operation 2: \(x \leftarrow (x + b) \bmod p\).

The symbol \(\bmod\) denotes the modulo operation. Determine whether it is possible to reach \(x=c\) after a positive number of operations. If it is possible, output Yes; otherwise, output No.

Note: The case of the output is not sensitive, meaning any capitalization of "yes" (e.g. YeS, yEs, etc.) is considered as Yes, and similarly for "No".

inputFormat

The input consists of four space-separated integers: \(p\), \(a\), \(b\), and \(c\).

outputFormat

Output a single line containing either Yes or No indicating whether it is possible to obtain \(c\) from \(0\) after performing a positive number of operations.

sample

7 3 2 6

Yes