Electron Cloud

   Time limit:   1 second

   Memory limit: 256 megabytes

PIC
Figure 1: *
The electron cloud of hydrogen atom

Electron cloud is not cloud consisting of electrons as it sounds like. It is a conception in modern atomic models to depict the range of an electron’s position with the probability of its passing the position at a time, unlike the previous method using by orbit model.

Electrons move in a rather high speed limited in an extremely small space, so that the macrocosm object laws of motion do not hold in this case. According to The Uncertainty Principle in quantum mechanics, it is out of the question to precisely measure the space coordinates and velocity of an electron at a certain time, needless to say about tracking its movement. Thus afterwards, scientists solved Schrodinger Equation to gain electron cloud model. In this model, the density of a point represents the probability of an electron’s emergences there. It is exactly named for the special cloud shape.

Studying these knowledge, Glory comes up with a simplified model. Suppose that an electron moves starting from the origin in the two-dimensional plane. At every unit interval, the electron will move upwards, downwards, leftwards and rightwards with an equal probability. He cares about the density of the electron cloud, namely the probability of the electron’s arrival, at some coordinates at some moment. Do you have some ideas?

Input

The input contains several test cases.

For each test case, there is one line containing three integers t, x and y, indicating the time, x-coordinate and y-coordinate as mentioned above, where 0 t,|x|,|y|≤ 10 000 000.

Output

For each test case, output a line containing an integer, representing the result of the density(a fraction) of the electron cloud at given coordinates (x,y) at given time t, modules 1 000 000 007.

Note: a
b ad (mod c) and bd 1 (mod c).

Sample Input

0 0 0

1 -1 0

4 1 1

Sample Input

1

250000002

843750006

Note

In the last sample, the density of the electron cloud at (1, 1) at 4-th unit intervals is -3
32.