Problem: Given an integer x. Your task is to find out how many positive integers n (1 ≤ n ≤ x) satisfy $$$n ⋅ a^n ≡ b   (mod\;p), where a, b, p$$$ are all known constants.

Input

The only line contains four integers a,b,p,x (2 ≤ p ≤ 10^6+3, 1 ≤ a,b < p, 1 ≤ x ≤ 10^{12}). It is guaranteed that p is a prime.

Output

Print a single integer: the number of possible answers n.

Examples

Input

2 3 5 8


Output

2


Input

4 6 7 13


Output

1


Input

233 233 10007 1


Output

1

Note

In the first sample, we can see that n=2 and n=8 are possible answers.

Solution (in JAVA):

Solution:
	import java.io.*;
	import java.math.BigInteger;
	import java.util.*;
import java.util.Map.Entry;

	
	public class Main
	{
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;
		private SpaceCharFilter filter;
		private PrintWriter pw;
		private long mod = 1000000000 + 7;
		
		private StringBuilder ans_sb;
		private int block;
		private long[] masks;
		private void soln()
		{
			/*int n = nextInt();
			int m = nextInt();
			String s = nextLine();
		//	debug(s);
			LinkedList<Integer>[] l1 = new LinkedList[n];
			LinkedList<Integer>[] l2 = new LinkedList[n];
			for(int i=0;i<n;i++) {
				l1[i] = new LinkedList<>();
				l2[i] = new LinkedList<>();
			}
			for(int i=0;i<n-1;i++) {
				int u = nextInt() - 1;
				int v = nextInt() - 1;
				l1[u].add(v);
				l2[v].add(u);
			}
		//	debug(l2);
			if(hhh(l1,n)) {
				pw.println(-1);
			}else {
			//	debug(l2);
				Stack<Integer> st = toposort(n,l1);
				boolean[] v = new boolean[n];
				int[][] dp = new int[n][26];
				while(!st.isEmpty()) {
					int x = st.pop();
					if(!v[x]) {
						dfs(x,-1,v,l2,s,dp);
					}
				}
				debug(dp);
				int max = 0;
				for(int i=0;i<n;i++)
					for(int j=0;j<26;j++)
						max = Math.max(max, dp[i][j]);
				pw.println(max);
			}*/
			long a = nextLong();
			long b = nextLong();
			long p = nextLong();
			long x = nextLong();
			long cnt = 0;
			for(long i = 0;i<=Math.min(x,p-2);i++) {
				long inv = pow(a, (p-2)*i, p);
		//		debug(i);
				long bdash = (b*inv)%p;
				long lim = (x-i)/(p-1);
			//	debug(bdash);
				long bddash = 0;
				if(i<bdash) {
					bddash = (i - bdash + p)%p;
				}else {
					bddash = i - bdash;
				}
				int tcnt = 0;
				if(bddash <= lim) {
					cnt++;
					tcnt++;
					tcnt += (lim - bddash)/p;
					cnt += (lim - bddash)/p;
				}
				//if(tcnt > 0)
			//	System.out.println(cnt+" "+i);
			}
			pw.println(cnt);
		}
		private void dfs(int v1, int prev, boolean[] v, LinkedList<Integer>[] l1,String s,int[][] dp) {
			Iterator<Integer> it = l1[v1].listIterator();
			v[v1] = true;
			while(it.hasNext()) {
				int x = it.next();
				if(!v[x]) {
					dfs(x,v1,v,l1,s,dp);
				}
			}
			dp[v1][s.charAt(v1)-'a']++;
			if(prev!=-1) {
				for(int i=0;i<26;i++)
					dp[v1][i] += dp[prev][i];
			}
		}
		private Stack<Integer> toposort(int n,LinkedList<Integer>[] l) {
			Stack<Integer> stack = new Stack<>();
			boolean[] v = new boolean[n];
			for(int i=0;i<n;i++) {
				if(!v[i])
					topo(i,v,stack,l);
			}
			return stack;
		}
		private void topo(int v1, boolean[] v,Stack<Integer> stack, LinkedList<Integer>[] l) {
			v[v1] = true;
			Iterator<Integer> it = l[v1].listIterator();
			while(it.hasNext()) {
				int x = it.next();
				if(!v[x]) {
					topo(x,v,stack,l);
				}
			}
			stack.push(v1);
		}
		private boolean hhh(LinkedList<Integer>[] l, int n) {
			boolean[] v1 = new boolean[n];
			boolean[] v2 = new boolean[n];
			for(int i=0;i<n;i++) {
				if(isCyclic(i,v1,v2,l))
					return true;
			}
			return false;
		}
		private boolean isCyclic(int v, boolean[] v1,boolean[] v2,LinkedList<Integer>[] l) {
			if(!v1[v]) {
				v1[v] = true;
				v2[v] = true;
				Iterator<Integer> it = l[v].listIterator();
				while(it.hasNext()) {
					int x = it.next();
					if(!v1[x]) {
						boolean f = isCyclic(x,v1,v2,l);
						if(f)
							return f;
						else if(v2[x]){
							return true;
						}
					}else if(v2[x])
						return true;
				}
			}
			v2[v] = false;
			return false;
		}
		private String solveEqn(long a, long b) {
	        long x = 0, y = 1, lastx = 1, lasty = 0, temp;
	        while (b != 0){
	        	long q = a / b;
	        	long r = a % b;
	            a = b;
	            b = r;
	            temp = x;
	            x = lastx - q * x;
	            lastx = temp;
	            temp = y;
	            y = lasty - q * y;
	            lasty = temp;
	        }
	        return lastx+" "+lasty;
		}
		private void debug(Object... o) {
			System.out.println(Arrays.deepToString(o));
		}
		
		private long pow(long a, long b, long c)
		{
			if (b == 0)
				return 1;
			long p = pow(a, b / 2, c);
			p = (p * p) % c;
			return (b % 2 == 0) ? p : (a * p) % c;
		}
	
		private long gcd(long n, long l)
		{
			if (l == 0)
				return n;
			return gcd(l, n % l);
		}
		public static void main(String[] args) throws Exception
		{
			/*new Thread(null, new Runnable()
			{
				@Override
				public void run()
				{
					new Main().solve();
				}
			}, "1", 1 << 25).start();*/
			new Main().solve();
		}
		public StringBuilder solve(){
			InputReader(System.in);
			/*try { 
				InputReader(new FileInputStream("C:\\Users\\hardik\\Desktop\\in.txt"));
			} catch(FileNotFoundException e) {}
			*/
			pw = new PrintWriter(System.out);
			//ans_sb = new StringBuilder();
			soln();
			
			pw.close();
			//System.out.println(ans_sb);
			return ans_sb;
		}
		public void InputReader(InputStream stream1)
		{
			stream = stream1;
		}
	
		private boolean isWhitespace(int c)
		{
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
	
		private boolean isEndOfLine(int c)
		{
			return c == '\n' || c == '\r' || c == -1;
		}
	
		private int read()
		{
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars)
			{
				curChar = 0;
				try
				{
					numChars = stream.read(buf);
				} catch (IOException e)
				{
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}
	
		private int nextInt()
		{
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-')
			{
				sgn = -1;
				c = read();
			}
			int res = 0;
			do
			{
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}
	
		private long nextLong()
		{
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-')
			{
				sgn = -1;
				c = read();
			}
			long res = 0;
			do
			{
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}
	
		private String nextToken()
		{
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do
			{
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}
	
		private String nextLine()
		{
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do
			{
				res.appendCodePoint(c);
				c = read();
			} while (!isEndOfLine(c));
			return res.toString();
		}
	
		private int[] nextIntArray(int n)
		{
			int[] arr = new int[n];
			for (int i = 0; i < n; i++)
			{
				arr[i] = nextInt();
			}
			return arr;
		}
	
		private long[] nextLongArray(int n)
		{
			long[] arr = new long[n];
			for (int i = 0; i < n; i++)
			{
				arr[i] = nextLong();
			}
			return arr;
		}
	
		private void pArray(int[] arr)
		{
			for (int i = 0; i < arr.length; i++)
			{
				System.out.print(arr[i] + " ");
			}
			System.out.println();
			return;
		}
	
		private void pArray(long[] arr)
		{
			for (int i = 0; i < arr.length; i++)
			{
				System.out.print(arr[i] + " ");
			}
			System.out.println();
			return;
		}
	
		private boolean isSpaceChar(int c)
		{
			if (filter != null)
				return filter.isSpaceChar(c);
			return isWhitespace(c);
		}
	
		private char nextChar()
		{
			int c = read();
			while (isSpaceChar(c))
				c = read();
			char c1 = (char) c;
			while (!isSpaceChar(c))
				c = read();
			return c1;
		}
	
		private interface SpaceCharFilter
		{
			public boolean isSpaceChar(int ch);
		}
	}