졸탄

마르톤의 친구 체로에게 양의 정수 $N$개로 이루어진 배열이 있다. 체로는 먼저 배열의 첫 번째 수를 칠판에 적는다. 그다음 두 번째 수를 첫 번째 수의 왼쪽이나 오른쪽에 적는다. 세 번째 수는 지금까지 적은 모든 수의 왼쪽이나 오른쪽에 적고, 남은 수도 배열 순서대로 같은 방식으로 하나씩 적는다.

마르톤은 이렇게 만들 수 있는 수열에서 가장 긴 강한 증가 부분 수열의 길이를 물었다. 부분 수열의 원소가 연속할 필요는 없다.

마르톤은 그런 부분 수열의 개수도 알고 싶어 한다. 체로가 만들 수 있는 모든 수열을 통틀어 가장 긴 강한 증가 부분 수열의 길이를 $M$이라 하자. 체로가 만들 수 있는 각 수열마다 길이가 $M$인 강한 증가 부분 수열의 개수를 세고, 그 값을 모두 더한 결과를 구하면 된다. 왼쪽과 오른쪽 선택이 한 번이라도 다르면 서로 다른 수열이고, 한 수열 안에서는 고른 위치가 하나라도 다르면 서로 다른 부분 수열이다.

이 개수는 매우 커질 수 있으므로 $10^9 + 7$로 나눈 나머지를 구한다.

체로는 지금 답을 구할 시간이 없어서 대신 구해 달라고 부탁했다.

첫째 줄에 정수 $N$이 주어진다. $(1 \le N \le 2 \times 10^5)$

둘째 줄에 체로의 배열 원소 $N$개가 공백으로 구분되어 주어진다. 각 원소는 $10^9$ 이하의 양의 정수다.

한 줄에 가장 긴 강한 증가 부분 수열의 길이와, 그 길이를 갖는 강한 증가 부분 수열의 개수를 $10^9 + 7$로 나눈 나머지를 공백으로 구분해 출력한다.

$N = 2$이고 배열이 $1, 1$인 경우를 보자. 만들 수 있는 가장 긴 강한 증가 부분 수열의 길이는 1이고, 그런 부분 수열은 모두 4개다.

첫 번째 방법은 첫 번째 1을 적은 뒤 두 번째 1을 오른쪽에 적는 것이다. 수열은 $1, 1$이 되고, 길이가 1인 강한 증가 부분 수열은 첫 번째 원소만 고른 것과 두 번째 원소만 고른 것으로 2개다.

두 번째 방법은 두 번째 1을 왼쪽에 적는 것이다. 수열은 역시 $1, 1$이고 부분 수열도 같은 방식으로 2개다. 두 경우를 더하면 4개다.