25182번 - 청정수열 (Hard)

문제

청정수열은 길이가 2ドルN$이고 1ドル$부터 $N$까지의 정수들이 정확히 두 번씩 등장하는 수열이다.

청정수열의 점수는 1ドル$이상 $N$이하인 모든 정수 $i$에 대해 다음 값의 합이다.

• (두 개의 $i$ 사이에 있는 수의 합) × $i$

이때, "사이"는 양 끝의 $i$를 포함한다.

길이가 2ドルN$인 청정수열의 최대 점수와 점수가 최대인 청정수열의 개수를 구해보자. 답이 매우 커질 수 있으니 10ドル^9+7$로 나눈 나머지를 출력한다.

입력

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

출력

첫째 줄에 길이가 2ドルN$인 청정수열의 점수의 최댓값을 10ドル^9+7$로 나눈 나머지와 점수가 최대인 청정수열의 개수를 10ドル^9+7$로 나눈 나머지를 공백을 사이에 두고 출력하라.

제한

힌트

예시로 $[3, 1, 2, 1, 3, 2]$는 $N$이 3ドル$인 청정수열이고 이 청정수열의 점수는 다음과 같이 계산되어 50ドル$점이 된다.

1ドル$과 1ドル$의 사이의 수들은 $[1,2,1]$ 이다. 따라서 $(1+2+1)\ ×\ 1$을 점수에 더한다.

2ドル$와 2ドル$의 사이의 수들은 $[2,1,3,2]$ 이다. 따라서 $(2+1+3+2)\ ×\ 2$를 점수에 더한다.

3ドル$과 3ドル$의 사이의 수들은 $[3,1,2,1,3]$ 이다. 따라서 $(3+1+2+1+3)\ ×\ 3$을 점수에 더한다.

따라서 이 청정수열의 점수는 4ドル+16+30$으로 50ドル$점이다.