1258. Count All Valid Pickup and Delivery Options

HardDynamic ProgrammingCombinatorial DP

Given n orders, each with a pickup and a delivery, count the sequences of all 2n events where every delivery comes after its own pickup. Return the count modulo 1000000007. The input is JSON {n}.

Input: JSON {n}.

Output: Integer — the number of valid sequences modulo 1e9+7.

Examples

Example 1 
Input: {"n":1}
Output: 1
Explanation: Pickup then delivery.
Example 2 
Input: {"n":2}
Output: 6
Explanation: Six valid orderings.
Example 3 
Input: {"n":3}
Output: 90
Explanation: Ninety valid orderings.

Constraints

Asked by

Google
Solve this problem in the editor →