406236: GYM102319 F Forever Young

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

F. Forever Youngtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Welcome to ACM Class! ACM Class has s students (1 ≤ s ≤ 106) of different ages, lined up along the wall to take attendance. The instructors Henry and Eugene each go from left to right and tick off everybody's name. They are bored of this menial task so they decide to play a game.

As Henry goes from left to right, he circles some students' names, following the rule that each student (after the first) is older than the last one he circled. Eugene circles some students' names so that each student is younger than the last one he circled. They are quite competitive, so using their they each circle as many names as possible, as they know every student's age.

They will be very happy if Henry circles exactly n (1 ≤ n ≤ s) names and Eugene circles exactly m (1 ≤ m ≤ s), their respective favourite numbers. Furthermore, they are quite high achievers so cumulatively they are hoping to circle lots of names. Thus n + m ≥ s - 50.

The class lines up differently every day. (Two lineups are different if at least one student is in a different position.) You'd like to keep Henry and Eugene happy for as long as possible to keep them from moving onto their next plan of starting World War 3. How long can you do this?

Input

The single line of input contains three space-separated integers s, n, and m (1 ≤ n, m ≤ s ≤ 106). It is guaranteed that n + m ≥ s - 50.

Output

Output the number of arrangements of the class that will make Henry and Eugene happy. This number can be quite large so output it modulo 109 + 7.

ExamplesInput
6 3 3
Output
256
Input
12 3 4
Output
213444

加入题单

上一题 下一题 算法标签: