F. Forever Young

Codeforces

IDCF10231F

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

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? 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 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. ## 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. [samples]

**Definitions** Let $ s, n, m \in \mathbb{Z}^+ $ with $ 1 \le n, m \le s \le 10^6 $ and $ n + m \ge s - 50 $. Let $ A = (a_1, a_2, \dots, a_s) $ be a permutation of $ s $ distinct ages (without loss of generality, $ \{1, 2, \dots, s\} $). **Constraints** 1. Henry selects a strictly increasing subsequence (by age) of length exactly $ n $, starting from the left, greedily. 2. Eugene selects a strictly decreasing subsequence (by age) of length exactly $ m $, starting from the left, greedily. 3. The union of the positions selected by Henry and Eugene covers at least $ s - 50 $ students: $ n + m \ge s - 50 $. **Objective** Count the number of permutations $ A $ of $ \{1, 2, \dots, s\} $ such that: - The length of the longest increasing subsequence (LIS) starting from the left (greedily) is exactly $ n $, - The length of the longest decreasing subsequence (LDS) starting from the left (greedily) is exactly $ m $, and output the count modulo $ 10^9 + 7 $.

API Response (JSON)

{
  "problem": {
    "name": "F. Forever Young",
    "description": {
      "content": "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 eve",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10231F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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 eve...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ s, n, m \\in \\mathbb{Z}^+ $ with $ 1 \\le n, m \\le s \\le 10^6 $ and $ n + m \\ge s - 50 $.  \nLet $ A = (a_1, a_2, \\dots, a_s) $ be a permutation of $ s $ distinct ages (without lo...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments