베라와 삼각관계

베라에게는 $0$번부터 $N-1$번까지 번호가 붙은 친구 $N$명이 있다. 모두 소프트웨어 공학을 전공하느라 연애할 시간이 없지만, 서로 짝사랑은 한다.

음이 아닌 정수 $x$에 대해 $g(x)$를 $x$를 이진법으로 쓴 결과에 들어 있는 $1$의 개수로 정의한다. 정수 상수 $A$, $B$, $M$을 써서 $f(i, j) = g((A \cdot B^{i \cdot N + j}) \bmod M)$으로 정의한다.

$i < j$인 친구 $i$와 $j$에 대해, $f(i, j)$가 짝수이면 $i$가 $j$를 짝사랑하고 홀수이면 $j$가 $i$를 짝사랑한다.

베라는 삼각관계를 재미있어한다. 삼각관계는 $i$가 $j$를, $j$가 $k$를, $k$가 $i$를 짝사랑하는 세 친구 $i$, $j$, $k$의 집합이다.

$N$, $M$, $A$, $B$가 주어질 때 베라의 친구 사이에 삼각관계가 몇 개 있는지 구하라. 세 친구의 집합이 다르면 두 삼각관계는 서로 다르다.

첫째 줄에 $N$, $M$, $A$, $B$가 공백으로 구분되어 주어진다.

제한:

• $3 \le N \le 200000$, $3 \le M \le 200000$
• $0 < A < M$, $0 < B < M$
• $N$, $M$, $A$, $B$는 정수이다.
• $M$은 소수이다.

삼각관계의 개수를 한 줄에 출력한다.

$a \to b$는 친구 $a$가 친구 $b$를 짝사랑한다는 뜻이다.

첫 번째 예제에서 $f(0, 1) = g(2) = 1$, $f(0, 2) = g(3) = 2$, $f(1, 2) = g(2) = 1$이다. 따라서 $0 \to 2$, $2 \to 1$, $1 \to 0$이고 삼각관계는 하나다.

두 번째 예제에서는 $1 \to 0$, $2 \to 0$, $2 \to 1$이므로 삼각관계가 없다.