Štef lives in a house located in (0, 0). His girlfriend Barica lives in a house located in (X, Y).

Štef likes walking, so he decided to walk for exactly N hours (starting from his house) and finish his route at Barica's house.

Each hour, Štef moves from his current position to one of the four adjacent positions (north, south, east or west).

Help Štef and calculate how manny possible routes there are. (If there isn't any, print 0.)

Input

In the first line there is an integer N (1 ≤ N ≤ 10⁶).

In the second line there are integers X, Y separated by a space (-N ≤ X, Y ≤ N).

Output

Calculate the number of possible Štef's routes from (0, 0) to (X, Y) that last for exactly N hours. Print the result modulo 500 000 003.

Example

Input:
3
2 1
Output:

3

Input:
2
0 0
Output:

4