Problem

A binary tree is a data structure characterized by the following properties:

• It can be an empty tree where root = null.
• It can consist of a root node that contains a value and two sub-trees labeled "left" and "right".
• Each sub-tree also follows the definition of a binary tree.

A binary tree is a binary search tree (BST) if all the non-empty nodes follow these two rules:

• If a node has a left sub-tree, then all the values in its left sub-tree are smaller than its value.
• If a node has a right sub-tree, then all the values in its right sub-tree are greater than its value.

Given an integer, determine the number of valid BSTs that can be created by nodes numbered from 1 to that integer. Please see the samples below for diagrams based on 1, 2 or 3 nodes.

Function Description

Complete the function numBST in the editor below.

numBST has the following parameter(s): int nodeValues[n]: the number of node values to analyze

Returns: int[n]:the number of different binary search trees that can be created for each test case modulo 1000000007(10^9 + 7).

Constraints

• 1 ≤ n ≤ 1000
• 1 ≤ nodeValues[i] ≤ 1000

Input Format for Custom Testing

Sample Case 0

Sample Input STDIN Function 5 nodeValues[] size n = 5 nodeValues = [1, 2, 3, 4, 100]

Output

The function returns an array of integers, each representing the number of unique BSTs for the corresponding input value modulo 1000000007.