405928: GYM102163 C Hasan and his lazy students

Hasan is teaching Dynamic Programming to his students at NCD. However, he feels they aren't studying what he is giving them, so he decided to test them on the NCDPC. He will give them an array of length $$$N$$$, and they must tell him how many Longest Increasing Subsequences are in the array.

For example, if the array is ($$$1$$$ $$$2$$$ $$$1$$$ $$$4$$$ $$$3$$$). The LIS's length is $$$3$$$, and it could be ($$$1$$$ $$$2$$$ $$$4$$$) or ($$$1$$$ $$$2$$$ $$$3$$$), so the answer is $$$2$$$. Note that you can't choose ($$$1$$$ $$$1$$$ $$$3$$$) because it must be a strictly increasing subsequence, and you can't choose ($$$1$$$ $$$2$$$ $$$3$$$ $$$4$$$) because you can't change the order of a subsequence.

First line of the input will be $$$T$$$, number of test cases.

Each test case starts with $$$N$$$, the size of the array, next line contain $$$N$$$ space separated integers, the array.

$$$1\le N \le 1000, 1 \le A_i \le 10^6 $$$

For each test case print one line, the length of the LIS and the number of LISes. As this number may be very large, print it module $$$10^9+7$$$

3
5
1 3 2 3 1
3
1 2 3
7
1 5 6 2 1 4 1

3 1
3 1
3 2