class Array
	def accum
		ac = Array.new(size + 1)
		ac[0] = 0
		(1..size).each do |i|
			ac[i] = ac[i-1] + self[i-1]
		end
		ac
	end
end

loop do
	n, s, w, q = gets.split.map(&:to_i)
	break if n == 0

	g = s
	a = Array.new(n)
	(0..n-1).each do |i|
		a[i] = g / 7 % 10
		g = (g.even? ?  g / 2 : (g / 2) ^ w)
	end
	a.reverse!

	k = 0
	if q == 2 || q == 5
		a.each_with_index do |x, i|
			k += n - i if x % q == 0
		end
		puts k
		next
	end

	t = 1
	mod = a.map do |x|
		y = x * t % q
		t = t * 10 % q
		y
	end
	mod_accum = mod.accum.map {|x| x % q}

	count = Hash.new(0)
	(0..n).each do |i|
		x = mod_accum[i]
		k += count[x] if i > 0 && a[i-1] > 0
		count[x] += 1
	end
	p k
end