Sum of Differences over Good Pairs

We define an ordered pair of non‐negative integers ((x,y)) as good if and only if it satisfies all of the following conditions:

1. \(0 \le x \le y\);
2. \(x+y = A\);
3. \(x \operatorname{AND} y = B\), where the bitwise AND operation is denoted by \(\operatorname{AND}\) (in C++ this is the operator &).

Given three non‐negative integers (A, B, M) (with (M > 0)), your task is to compute the sum of (y-x) over all good pairs ((x,y)) modulo (M).

Formally, you need to compute

[ S = \left(\sum_{\substack{x,y \ge 0 \ \text{good}(x,y)}} (y - x)\right) \bmod M, ]

where good(x,y) is true exactly when ((x,y)) is a good pair.

Problem Reduction

It is useful to make the substitution (x = B + p) and (y = B + q). Since (x+y=A) this implies that (p+q = A-2B). Denote (R = A-2B). In order for the decomposition in binary to work without any carries, it is necessary that (R \ge 0) and (R) has no bit in common with (B), i.e. (R ;&; B = 0).

For every bit position (i) such that the (i)th bit of (R) is (1) (with (B)'s corresponding bit being (0)), one must choose either to add (2^i) to (p) or to (q) but not to both (choosing both is forbidden because then the corresponding bit in (x \operatorname{AND} y) would be (1) in a position where (B) has (0)). Notice that the contribution to (y-x) becomes (q-p). When we analyze the valid assignments satisfying (p \le q) (which is equivalent to (x \le y)), one finds that if the number of bits set in (R) is (k) and if (H) denotes the highest power of (2) among the bits in (R), then the sum over all valid assignments equals

[ \begin{cases} 0, & \text{if } R = 0,\ 2^{k-1} \cdot H, & \text{if } R > 0. \end{cases} ]

If either (R < 0) or (R ;&; B \neq 0) then no good pairs exist and the answer is 0. Finally, output the answer modulo (M).

Input and Output Format

The input consists of three non-negative integers (A, B, M) in one line separated by spaces.

The output is a single integer representing the computed sum modulo (M).

inputFormat

The input contains three space-separated non-negative integers A, B and M (M > 0), in one line.

For example:

4 1 100

outputFormat

Output a single integer: the sum of \(y-x\) over all good pairs \((x,y)\) modulo M.

sample

4 1 100

2