National Olympiad in Informatics, China, 2007
Recently, Alex has made shocking advances in the technique of counting spanning trees in undirected, connected graphs. He discovered:
- A cycle with nodes contains distinct spanning trees.
- A complete graph with nodes contains distinct spanning trees.
These two discoveries have made Alex ecstatic, so he would like to continue on his adventure of counting spanning trees. That is, he would like to be able to count the number of spanning trees in all kinds of different graphs.
One day, Alex is meeting up with his peers. Everyone sat in a circle around a big round table. After taking a look, Alex immediately recalls his spanning tree problem. If he considers each of his peers as a node and neighboring peers (nodes with a distance of between them) to be connected by an edge, then this becomes a cycle. However, Alex has already mastered calculations on cycles and is not really interested anymore. So, he changed the graph up a bit: Not only does he add an edge between neighboring peers, but he also adds an edge between pairs of peers who are separated by a single seat (nodes with a distance of between them). Now, he considers peers connected by a single edge to be adjacent, as depicted in the following figure.
Alex has never tried counting spanning trees on this kind of graph before, however, he recalls his teacher explaining that there is a general method for counting the number of spanning trees on any type of graph. First, construct an matrix such that:
where represents the degree of node .
Let's construct the matrix corresponding to the graph of the round table as depicted above. To count the number of spanning trees, we only have to remove the last row and column of , obtaining an matrix which we shall call . Computing the determinant of matrix will yield the number of spanning trees in the graph above.
Therefore the number of spanning trees in this graph is . Alex noticed that using the general method, calculations are very complex and tedious. Yet, he cannot find any other formulas that are simpler than this. So, he simplified the graph. At some place, he broke apart the circle around the table. This way, his peers form a chain of nodes, where an edge exists between all pairs of nodes with a distance of or a distance of between them. The case for nodes is depicted below:
This way, the total number of spanning trees is reduced by a great amount. Alex just thinks and thinks, until the entire meeting is over. Finally, he comes up with an efficient method to count the number of spanning trees in this graph. However, if he also decides to join nodes with a distance of , then once again he will not know how to find the answer efficiently. Please help Alex count the number of spanning trees in these types of graphs!
Input Specification
The input contains two integers and , separated by a space. means that all nodes with a distance no greater than are to be linked by an edge in the graph. indicates that there are total nodes.
Output Specification
Output a single integer, the number of spanning trees in the graph. Since the answer can be rather large, you are required to output the answer modulo .
Sample Input
3 5
Sample Output
75
Explanation
The graph for the sample is depicted below:
Constraints
For all the test cases, .
Test Case | Range of | Range of | Test Case | Range of | Range of |
---|---|---|---|---|---|
Hints
One method to compute the determinant is to first let represent the number of inversions in the sequence . Then, the determinant of is calculated using the formula:
If , then the calculations are as follows:
Therefore the determinant of is .
Problem translated to English by .
Comments