目标房号出现几次

题目描述

给定 a、n、m、target，统计 a^1,a^2,…,a^n 中模m余数等于target的项数。n=0时序列为空。

输入格式

一行输入 a、n、m、target，满足 0≤a≤10^9、0≤n≤10^18、1≤m≤2×10^5、0≤target<m。

输出格式

输出符合条件的指数位置数量；n=0时输出0。

样例

输入

2 20 5 1

输出

5