#abc220e. [abc220_e]Distance on Large Perfect Binary Tree
[abc220_e]Distance on Large Perfect Binary Tree
Problem Statement
We have a tree with vertices.
The vertices are numbered through . For each , the following edges exist:
- an undirected edge connecting Vertex and Vertex ,
- an undirected edge connecting Vertex and Vertex .
There is no other edge.
Let the distance between two vertices be the number of edges in the simple path connecting those two vertices.
Find the number, modulo , of pairs of vertices such that the distance between them is .
Constraints
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
Output
Print the answer.
Sample Input 1
Sample Output 1
The following figure describes the given tree.
There are pairs of vertices such that the distance between them is : .