Sau dịp nghỉ Tết Nguyên Đán 2021, A519PhuongDN đã trở thành một con người bài bạc. Với chiếc điện thoại trong tay, A519PhuongDN có thể gạ solo tiến lên miền Nam ở bất cứ mọi nơi.

Vào một ngày đẹp trời, sau khi chơi qua hàng nghìn ván tiến lên miền Nam, cô bắt đầu cảm thấy chán. Thấy rằng kiếp đỏ đen bài bạc của mình quá phình phường, lại sực nhớ ra A519 đang mở server minecraft, cô bắt tay ngay vào công cuộc tạo nên một mod tiến lên miền Nam trong minercraft.

Là một trò chơi may rủi, cô sẽ phải dùng hàm RNG để sinh ra các trường hợp chia bài cho mỗi người chơi. Số p[i] của lần chơi thứ n được hàm RNG sinh ra có công thức tính như sau:

\(p[i] = x^{p[i - 1]} \mod (10^9 + 7)\)

với số p[i] trong tay, cô nắm bắt được vận mệnh của mình trong mọi ván bài. Nếu như số p[i] mod 2 là số lẻ thì cô sẽ luôn về nhất trong ván bài thứ i. Vì máy tính của cô là máy văn phòng đã vậy còn đang chạy minecraft nên rất ngốn cấu hình, A519PhuongDN nhờ các bạn tính số p[n] ở trận thứ n để cô biết được lúc nào nên all in, tạo tiền đề đạp đổ vị trí người giàu nhất server của CarlavierVN, biết rằng mỗi ván bài tốn 10 phút để hoàn thành và server của CarlavierVN còn 87 ngày nữa là sẽ bắt buộc phải đóng cửa.

Input

• Dòng \(1\) chứa hằng số \(x \le 10^9\).
• Dòng \(2\) chứa số \(p[1]\) là số đã được sinh trong trận cô đang chơi \((p[i] \le 10^9)\).
• Dòng \(3\) chứa số \(n\) là ván cô cần tính được số ngẫu nhiên mà máy tính sinh ra \((n \le 10^5)\).

Output

• In ra YES nếu A519PhuongDN về nhất, nếu ngược lại thì in ra NO.

Example

2
3
2

NO