LCC/Moose '20 Contest 2 S5 - AlanLiChess2004

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

Alan is extremely good at chess. So much so that beating his opponents has gotten boring. Thus, Alan has begun playing a new version of chess on an infinite chessboard. Often in these games, Alan must maneuver his knight from some square (which we will define to be (0,0)) to another square (x,y). Alan wants to know how many ways there are to do so in N moves. Can you help him?

In chess, a knight can move from (a, b) to (a \pm 1, b \pm 2) or (a \pm 2, b \pm 1).

Input Specification

The only line of input will contain 3 integers: N\ (0 \leq N \leq 5\cdot 10^3),x,y\ (-10^4 \leq x,y \leq 10^4).

Output Specification

The only line of output is to contain 1 integer: the number of ways modulo 10^9 + 7.


Subtask 1 (5%)

N \leq 200

Subtask 2 (95%)

No further constraints.

Sample Input

2 0 0

Sample Output


Sample Explanation

Alan can make any valid knight move, and then undo it.

Valid moves include: (1, 2), (-1, -2), (1, -2), (-1, 2), (2, 1), (-2, -1), (-2, 1), (2, -1)


There are no comments at the moment.