import random

m = int(input())
d = int(input())
n = int(input())
b = int(input())

def fast(m,d,n,b):
	v = [[0] * b for i in range(60)]
	for i in range(b):
		if (i+d)%b != 0:
			v[0][i] = pow(i+d, i, b)
		else:
			v[0][i] = 0

	for i in range(59):
		for j in range(b):
			v[i+1][j] = v[i][v[i][j]]

	if n == 0:
		r = '0123456789ABCDEFG'
		return r[m % b]

	if m == 0:
		n -= 1
		m = pow(m + d, m, b)

	m %= b
	for i in range(60):
		if (n >> i) & 1:
			m = v[i][m]

	r = '0123456789ABCDEFG'
	return r[m]

def naive(m,d,n,b):
	if n == 0:
		r = '0123456789ABCDEFG'
		return r[m % b]
	if m == 0:
		n -= 1
		m = pow(m+d, m, b)
	m %= b
	for i in range(n):
		if (m+d)%b != 0:
			m = pow(m+d, m, b)
		else:
			m = 0
	
	r = '0123456789ABCDEFG'

	return r[m]

print(fast(m,d,n,b))