atcoder#ABC288H. [ABC288Ex] A Nameless Counting Problem
[ABC288Ex] A Nameless Counting Problem
Score : points
Problem Statement
Print the number of integer sequences of length , , that satisfy both of the following conditions, modulo .
Here, denotes bitwise XOR.
What is bitwise XOR?
The bitwise XOR of non-negative integers $A$ and $B$, $A \oplus B$, is defined as follows.
- When $A \oplus B$ is written in binary, the $k$-th lowest bit ($k \geq 0$) is $1$ if exactly one of the $k$-th lowest bits of $A$ and $B$ is $1$, and $0$ otherwise.
Constraints
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
Output
Print the answer.
3 3 2
5
Here are the five sequences of length that satisfy both conditions in the statement: $(0, 0, 2), (0, 1, 3), (1, 1, 2), (2, 2, 2), (2, 3, 3)$.
200 900606388 317329110
788002104