Counting Magic Sequences

Given four integers n, x, y and p, count the number of sequences {a₀, a₁, …, a_n} satisfying the following properties:

• a₀ = 0.
• For every i with 1 ≤ i ≤ n, a_i = a_i-1 + x or a_i = a_i-1 + y.
• For every i with 1 ≤ i ≤ n, p does not divide a_i (i.e. a_i mod p ≠ 0).

Two sequences are considered different if there exists at least one index i such that the i-th elements are different. Output the count of such sequences modulo \(10^9+7\).

Note: The answer must be computed modulo \(10^9+7\). It is guaranteed that p is an integer greater than 1.

inputFormat

The input consists of a single line containing four space‐separated integers:

n x y p

n denotes the number of moves (the sequence has n+1 terms), x and y are the possible increments, and p is the modulus in the divisibility restriction.

outputFormat

Output a single integer — the number of valid sequences, modulo \(10^9+7\).

sample

1 2 3 5

2