배수 찾기

숫자들로 이루어진 수열 $a_0 a_1 \cdots a_{N-1}$ 과 소수 $Q$ 가 주어진다. $a_i \ne 0$ 인 모든 인덱스 쌍 $i \le j$ 에 대해, 부분 수열 $a_i a_{i+1} \cdots a_j$ 는 하나의 양의 정수를 십진법으로 나타낸 것으로 볼 수 있다. 앞자리가 $0$ 인(즉 $a_i = 0$ 인) 부분 수열은 고려하지 않는다. 대응하는 정수가 $Q$ 의 배수가 되는 쌍 $(i, j)$ 의 개수를 세는 것이 목표이다.

입력은 최대 $50$ 개의 데이터셋으로 이루어진다. 각 데이터셋은 공백으로 구분된 네 정수 $N$, $S$, $W$, $Q$ 가 담긴 한 줄이며, $1 \le N \le 10^5$, $1 \le S \le 10^9$, $1 \le W \le 10^9$ 이고 $Q$ 는 $10^8$ 보다 작은 소수이다. 길이 $N$ 의 수열 $a_0 \cdots a_{N-1}$ 은 아래 코드로 생성되며, 여기서 $a_i$ 는 a[i] 로 표기한다.

int g = S;
for(int i=0; i<N; i++) {
    a[i] = (g/7) % 10;
    if( g%2 == 0 ) { g = (g/2); }
    else           { g = (g/2) ^ W; }
}

여기서 /, %, ^ 는 각각 정수 나눗셈, 나머지, 비트 단위 배타적 논리합(XOR)이다. 이 코드는 단지 유사 난수 생성기일 뿐이며, 의도된 풀이는 수열이 어떻게 생성되는지에 의존하지 않는다.

입력의 끝은 공백으로 구분된 네 개의 $0$ 이 담긴 줄로 표시된다.

각 데이터셋에 대해 답을 한 줄에 출력한다. 답은 $2^{30}$ 보다 작다고 가정해도 된다.

같은 수라도 그 수를 만들어 내는 위치 쌍 $(i, j)$ 마다 따로 센다. 예를 들어 수열이 $421$ 이고 $Q = 7$ 이면 $7$ 의 배수는 $42$ 와 $21$ 이므로 답은 $2$ 이다. 수열이 $5052$ 이고 $Q = 5$ 이면 $5$ 의 배수는 $5$, $50$, $505$, 그리고 다시 $5$ 로 모두 $4$ 개이다. $0$ 이나 $05$ 는 세지 않는데, 고려하는 부분 수열은 반드시 $0$ 이 아닌 자리에서 시작해야 하며(앞자리 $0$ 금지) 양의 정수를 나타내야 하기 때문이다. 숫자 $5$ 는 서로 다른 두 위치에 나타나므로 두 번 센다. 참고로, 샘플 입력의 처음 네 데이터셋은 각각 수열 $421$, $5052$, $95073$, $12221$ 을 생성한다.