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)~.
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)~.
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.
2 0 0
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)~