#include <map>
#include <vector>
#include <iostream>
using namespace std;
int main() {
	int N, S, W, Q;
	while (cin >> N >> S >> W >> Q, N) {
		vector<int> A(N);
		for (int i = 0; i < N; ++i) {
			A[i] = (S / 7) % 10;
			if (S % 2 == 0) S /= 2;
			else S = (S / 2) ^ W;
		}
		long long ans = 0;
		if (Q == 2 || Q == 5) {
			int cnt = 0;
			for (int i = 0; i < N; ++i) {
				if (A[i] != 0) ++cnt;
				if (A[i] % Q == 0) ans += cnt;
			}
		}
		else {
			map<int, int> tbl;
			++tbl[0];
			int pw = 1, tailsum = 0;
			for (int i = N - 1; i >= 0; --i) {
				tailsum = (tailsum + 1LL * A[i] * pw) % Q;
				if (A[i] != 0) ans += tbl[tailsum];
				++tbl[tailsum];
				pw = 10LL * pw % Q;
			}
		}
		cout << ans << endl;
	}
	return 0;
}
