WALK1 - Štef and Barica
Š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:
|
|
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 |