How Many Longest Increasing

Difficulty: 1700 6000 ms 128 MB

dp

Print the NUMBER of longest strictly-increasing subsequences, modulo 10⁹+7.

Input: the first line has N; the second line has N integers.

Output: the count of LIS of maximum length, mod 10⁹+7.

Constraints:

• 1 ≤ N ≤ 5000 (tests use N ≤ 1500)
• |a_i| ≤ 10⁹

Sample Tests

5
1 3 5 4 7

2

3
2 2 2

3

Read the Editorial