We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Extremum Permutations

Extremum Permutations

Problem
Submissions
Leaderboard
Discussions
Editorial

Let's consider a permutation P = {p1, p2, ..., pN} of the set of N = {1, 2, 3, ..., N} elements .

P is called a magic set if it satisfies both of the following constraints:

  • Given a set of K integers, the elements in positions a1, a2, ..., aK are less than their adjacent elements, i.e., pai-1 > pai < pai+1
  • Given a set of L integers, elements in positions b1, b2, ..., bL are greater than their adjacent elements, i.e., pbi-1 < pbi > pbi+1

How many such magic sets are there?

Input Format
The first line of input contains three integers N, K, L separated by a single space.
The second line contains K integers, a1, a2, ... aK each separated by single space.
the third line contains L integers, b1, b2, ... bL each separated by single space.

Output Format
Output the answer modulo 1000000007 (109+7).

Constraints
3 <= N <= 5000
1 <= K, L <= 5000
2 <= ai, bj <= N-1, where i ∈ [1, K] AND j ∈ [1, L]

Sample Input #00

4 1 1
2
3

Sample Output #00

5

Explanation #00

Here, N = 4 a1 = 2 and b1 = 3. The 5 permutations of {1,2,3,4} that satisfy the condition are

  • 2 1 4 3
  • 3 2 4 1
  • 4 2 3 1
  • 3 1 4 2
  • 4 1 3 2

Sample Input #01

10 2 2
2 4
3 9

Sample Output #01

161280

Author

Seyaua

Difficulty

Medium

Max Score

100

Submitted By

772

Need Help?


View discussions
View editorial
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits

Choose a translation


  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature