### main

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

  ais = n.times.map{0}
  g = s
  for i in (0...n)
    ais[i] = (g / 7) % 10
    g = (g % 2 == 0) ? g / 2 : (g / 2) ^ w
  end  

  if q == 2 || q == 5
    nzs = 0
    count = 0
    for i in (0...n)
      nzs += 1 if ais[i] != 0
      count += nzs if ais[i] % q == 0
    end

    puts count
    next
  end
  
  mds = (n + 1).times.map{0}
  tmd = 1

  (n - 1).downto(0) do |i|
    mds[i] = (ais[i] * tmd + mds[i + 1]) % q
    tmd = (tmd * 10) % q
  end

  chash = Hash.new{0}
  chash[0] = 1
  count = 0
  
  (n - 1).downto(0) do |i|
    mdi = mds[i]
    if ais[i] != 0 && chash.include?(mdi)
      count += chash[mdi]
    end
    chash[mdi] += 1
  end
  
  puts count
end