944. Number of Ways to Reorder Array as BST

Given an array nums of distinct integers, inserting them in order builds a binary search tree. Return the number of different orderings of nums that produce the exact same BST, excluding the original ordering itself, modulo 1,000,000,007. The input is a JSON array.

Input: A JSON array of distinct integers.

Output: Integer — the count of reorderings mod 1e9+7.

Examples

Input: [3,4,5,1,2]
Output: 5
Explanation: Five other orderings yield the same BST.

Input: [2,1,3]
Output: 1
Explanation: One other ordering.

Input: [1]
Output: 0
Explanation: No other ordering.

Constraints

• 1<=n<=1000
• values distinct

Asked by