Chichi’s Home Work

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 thats why Gohan cant 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 Input consists of several lines each contains 3 integers: N, x, y (1 ≤ N ≤ 1,000 and 1 ≤ x < y ≤ N). Output 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 624 500 35 67 Sample Output 57 774474320