B. Baseball Court

After lengthy meetings on the subject, the NCPC jury has decided that getting the contestants' blood pumping would result in better contests. Thus they figured it would be a good idea to compete for bragging rights in some kind of sport prior to the programming contest. For this they need some place to compete and to pick a sport to compete in. One of those is solved easily by drawing at random from a hat, which results in the chosen sport being baseball. That simply leaves the matter of making a suitable court to play on. The NCPC jury has access to a rectangular plot of land \(a\) by \(b\) meters in size. Furthermore, they have \(N\) square tiles of grass \(1\) by \(1\) meter in size they can place on this plot to create the court. All grass tiles must be placed with their sides parallel to the edges of the plot.

The south-west corner of the land is chosen to be the batting point. For the placement of the grass tiles to constitute a valid court, two conditions must be met. Firstly, for any given tile the south and west sides must either lay directly against the edge of the plot or directly against another tile. This is required to make sure the ball doesn't exit and reenter the court while following a straight trajectory. Secondly, all tiles which have no adjacent tile to the north nor to the east must have the same manhattan distance from the batting point. This is to prevent batters from preferring some directions over others.

Your task is to find the number of ways to place the tiles so that it creates a valid baseball court.

The first line of the input contains a single positive integer \(N\) (\(1 \leq N \leq 10^4\)), the number of grass tiles available. The second line of the input contains two positive integers \(a\) and \(b\) (\(1 \leq a, b \leq 10^4\)), the size of the land the court can be made within.

Print the number of valid ways to place the grass tiles to make up a baseball court. All \(n\) grass tiles must be used. Since this number might be very large, print the answer modulo \(10^9 + 7\).

생성자가 기록되지 않았습니다.

출처 ICPC NCPC 2024