import java.io.*;
import java.util.*;

public class crack_mb {
    public static void main(String[] args) throws IOException {
	Scanner in = new Scanner(new File("crack.in"));
	int x = in.nextInt();
	int m = in.nextInt();
	int l = in.nextInt();
	int v = in.nextInt();
	in.close();
	
	for (int cheat = 0; ; ++cheat) {
	    int xv = x;
	    int cc = cheat;
	    int res = 0;
	    for (int i = 0; i < 9; ++i) {
		res = (res + xv * (cc % 10)) & (m - 1);
		xv = (xv * x) & (m - 1);
		cc /= 10;
	    }
	    if (res == v) {
		StringBuilder sb = new StringBuilder();
		sb.append(0);
		for (int i = 0; i < 9; ++i) {
    		    sb.append(cheat % 10);
		    cheat /= 10;
		}
		for (int i = 10; i < l; ++i) {
		    sb.append(0);
		}
		
		PrintWriter out = new PrintWriter("crack.out");
		out.println(sb);
		out.close();
		return;
	    }
	}
    }
}
