Problem C

Chichi’s Home Work

Time Limit: 3 Second

As you know Chichi always wants her son to study and keep him busy so that he does not get time to think about battling. And that’s why Gohan can’t go out to play with you, her mom thinks Gohan will escape and have a practice session with Krialen. So she gave a home work to Gohan and said, “OK! If you are done with this home work before evening then you can go out for just one hour!”

One hour! Such a short time! But that does not matter for Gohan, he just wants to go out. So he was very glad. But it took no time to fade his smile. The task is so tough … can you help him?

How many ways to draw 6 half circles so that none of them intersect and 2nd one ends after 4th one ends (not necessarily immediately after 4th one ends)? One of the possible solutions is:

There are totally 80 ways.

Input and Output:

Input consists of several lines each contains 3 integers: N, x, y ( 1 ≤ N ≤ 1,000 and 1 ≤ x < y ≤ N ). You are to output the number of ways you can draw N half circles so that x th one ends after y th one. As the answer will be very big so you have to output it by mod 1,000,000,000.

SAMPLE INPUT	OUTPUT FOR SAMPLE INPUT
6 2 4 500 35 67	80 233132320

Problemsetter: Md. Mahbubul Hasan

Special Thanks to: Tasnim Imran Sunny