#arc163d. [arc163_d]Sum of SCC
[arc163_d]Sum of SCC
Problem Statement
Consider a directed graph with vertices numbered to that satisfies all of the following conditions.
-
is a tournament. In other words, has no multi-edges or self-loops, and for any two vertices of , exactly one of the edges and exists.
-
Among the edges of , exactly are directed from a vertex with a smaller number to a vertex with a larger number.
Find the total number of strongly connected components over all such directed graphs , modulo .
Constraints
Input
The input is given from Standard Input in the following format:
Output
Print the answer.
Sample Input 1
3 1
Sample Output 1
7
Below are the three directed graphs that satisfy the conditions. The numbers of their strongly connected components are from left to right, so the answer is .
Sample Input 2
6 2
Sample Output 2
300
Sample Input 3
25 156
Sample Output 3
902739687