Дано бесконечное множество, сгенерированное следующим образом:
- \(1\) принадлежит множеству.
- Если \(x\) принадлежит множеству, то \(x \cdot a\) и \(x+b\) также принадлежат множеству.
Например, если \(a=3\) и \(b=6\), то первые пять элементов множества равны:
- \(1\),
- \(3\) (\(1\) лежит в множестве, поэтому \(1\cdot a=3\) лежит в множестве),
- \(7\) (\(1\) лежит в множестве, поэтому \(1+b=7\) лежит в множестве),
- \(9\) (\(3\) лежит в множестве, поэтому \(3\cdot a=9\) лежит в множестве),
- \(13\) (\(7\) лежит в множестве, поэтому \(7+b=13\) лежит в множестве).
Даны положительные целые числа \(a\), \(b\), \(n\). Выясните, принадлежит ли \(n\) множеству.
Выходные данные
Для каждого набора входных данных выведите «Yes», если \(n\) принадлежит множеству, и «No» иначе. Вы можете выводить каждую букву в любом регистре (строчную или заглавную).
Примечание
В первом наборе \(24\) генерируется следующим образом:
- \(1\) лежит в множестве, поэтому \(3\) и \(6\) лежат в множестве;
- \(3\) лежит в множестве, поэтому \(9\) и \(8\) лежат в множестве;
- \(8\) лежит в множестве, поэтому \(24\) и \(13\) лежат в множестве.
Таким образом, \(24\) принадлежит множеству.
Первые пять элементов множества из второго набора входных данных описаны в условии. Можно заметить, что \(10\) не в их числе.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
24 3 5
10 3 6
2345 1 4
19260817 394 485
19260817 233 264
|
Yes
No
Yes
No
Yes
|