Migrated from Lutece 3034 递推数列

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

给你们机会去签到，但请最好别死在分类讨论上，出题人让你分类讨论绝不是为了刁难你，只是想考验你对一些数论性质的理解是否到位。

maco 酝酿出了这样一个递推数列： $a_{n+1}=(k\cdot a_n+m) \enspace mod \enspace p$ $k,m,p,a_0$是这个数列递推式已知的参数，其中 $p$ 是一个质数 对于某个非负整数 $t$ ，请你判断是否存在非负整数 $i$，使得 $a_i=t$ ？

如果死在了分类讨论上，那就是没好好听课。。。。。（好气） maco上课都讲这么认真了，如果没学过数论的话，真的一定要认真听啊啊啊啊啊~~~（哭死） 如果你没能跟上，也一定请认真钻研maco的ppt好嘛，答应maco，这次一定！

（请注意 $p$ 的范围是 $10^9$，居然有人写暴力。。。。。）

Input

输入五个非负整数：$k,m,p,a_0,t$

Output

如果存在，输出"YES"，否则，输出"NO"

Samples

2 3 13 5 11

YES

3 2 13 5 10

NO

Constraints

$2≤p≤10^9$ $0≤k,m,a_0,t≤p-1$

Resources

2023 UESTC ICPC Training for Math