Challenge
Return [length, count] for the longest strictly increasing subsequences. Subsequences retain index order but need not be contiguous. Two subsequences are distinct if their index sequences differ, even when their values are equal. Return count modulo 1,000,000,007. This extends the existing subsequence-length exercise: both optimum length and the number of optimum choices are required.
Input and output contract
0 ≤ n ≤ 40,000; integer values with absolute value ≤ 1,000,000. Empty input returns [0, 0]. Equal adjacent selected values are never increasing. u is distinct values.
All tests follow this contract. You do not need to validate malformed input. Return the requested result from longest_increasing_subsequences; printed output is not your answer. Standard-library tools are allowed. Implement your solution in Python 3.12.
Target complexity: O(n log(u + 1)) time; O(u) auxiliary space
Return values are checked by type. Use the exact function name. Print output is not your answer. Tests have time and memory limits.
Public examples
Arguments
[[1, 3, 5, 4, 7]]
Expected return
[4, 2]
Arguments
[[2, 2, 2]]
Expected return
[1, 3]
Arguments
[[]]
Expected return
[0, 0]
Hint
For each value, query the best (length, count) among earlier STRICTLY smaller values. A Fenwick tree can aggregate these pairs after coordinate compression.
The worked solution unlocks after completion, or with Premium access.