WALK1 - Štef and Barica

no tags 

Š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 many possible routes there are. (If there aren't any, print 0.)

Input

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

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

hide comments
smso: 2022-07-26 07:20:16

more testcases:
3
2 1
3

4
2 1
0

5
2 1
50

6
2 1
0

7
2 1
735

8
2 1
0

Rohan Jain: 2014-12-01 23:03:23

Really nice question...:D

Adrian Satja Kurdija: 2011-11-05 11:26:10

Thank you! :)

Alex Anderson: 2011-11-05 05:55:18

This is an excellent problem.


Added by:Adrian Satja Kurdija
Date:2011-10-30
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:that would be me