#agc062e. [agc062_e]Overlap Binary Tree
[agc062_e]Overlap Binary Tree
Problem Statement
You are given an odd number and a non-negative integer .
Find the number, modulo , of sequences of integer pairs satisfying all of the following conditions.
- is a permutation of the integers from to .
- .
- .
- There are exactly indices such that .
- There is a rooted binary tree with vertices numbered from to such that the following holds:
- vertices and have an ancestor-descendant relationship in intervals \[L_i,R_i\] and \[L_j,R_j\] intersect.
Here, a rooted binary tree is a rooted tree where each vertex has or children. Vertices and are said to have an ancestor-descendant relationship in a tree if either vertex exists on the simple path connecting the root to vertex , or vice versa.
Constraints
- is odd.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
Output
Print the answer.
Sample Input 1
3 1
Sample Output 1
2
For example, if , then is the only pair with . Also, the fifth condition is satisfied by a tree where vertex is the root, and its children are vertices and .
Sample Input 2
1 0
Sample Output 2
0
Sample Input 3
521 400
Sample Output 3
0
Sample Input 4
199999 2023
Sample Output 4
283903125