Description

Dahe has some socks, but they are often piled up messily.

One day, Long'er couldn’t stand it anymore, so she placed the socks onto a sequence (called the sock sequence).

Each sock has a $dirty$ value. Define the $dirty$ value of the sock sequence as $\max \left( (dirty_{l} \ bitand \ dirty_{l+1} \ bitand \ \cdots \ bitand \ dirty_{r}) + (dirty_{l} \ bitor \ dirty_{l+1} \ bitor \ \cdots \ bitor \ dirty_{r}) \right)$, where $dirty_{i}$ denotes the $dirty$ value of the $i$-th sock; $bitand$ means bitwise AND (in C++ it is &), and $bitor$ means bitwise OR (in C++ it is |).

In short, find a contiguous subsequence that maximizes the sum of the bitwise AND and the bitwise OR of all numbers in it.

If the $dirty$ value of this sock sequence reaches a certain threshold, then Long'er will dislike Dahe.

Of course, Dahe doesn’t want that, so she wants to know the $dirty$ value of this sock sequence.

Input Format

The first line contains three integers $n, b, p$, representing the length of the sequence and output-related parameters.

The second line contains $n$ integers, the initial values of the sequence.

Output Format

Let the answer be $x$. You need to output $(x+233)^{b} \,\, \text{mod} \,\,p$.

10 1 10000000
7 9 9 4 0 0 8 8 4 7

251

Hint

$1 \le n, p \le 10^{5}$.

$0 \le b, dirty_{i} \le 10^{7}$.

For the testdata of test points $1$ and $2$, it is guaranteed that $1 \le n \le 100$.

Translated by ChatGPT 5