청정수열 (Hard)

시간 제한1초메모리 제한1024 MB

요약

N이 주어질 때, 1부터 N까지 각 수가 두 번씩 나타나는 수열 중 점수가 최대인 값과 그 값을 만드는 수열의 개수를 10^9+7로 나눈 나머지로 구합니다.

문제

청정수열은 길이가 $2N$ 이고, $1$ 부터 $N$ 까지의 정수가 각각 정확히 두 번씩 들어 있는 수열이다.

청정수열의 점수는 $1$ 이상 $N$ 이하인 모든 정수 $i$ 에 대해 다음 값을 구한 뒤 모두 더한 합이다.

여기서 사이에는 양 끝의 $i$ 도 포함한다.

길이가 $2N$ 인 청정수열 중 점수의 최댓값과, 그 최댓값을 갖는 청정수열의 개수를 구한다. 답이 매우 커질 수 있으므로 각각 $10^9+7$ 로 나눈 나머지를 구한다.

첫째 줄에 정수 $N$ 이 주어진다 ( $1$ 이상 $10^5$ 이하).

첫째 줄에 청정수열 점수의 최댓값을 $10^9+7$ 로 나눈 나머지와, 점수가 최대인 청정수열의 개수를 $10^9+7$ 로 나눈 나머지를 공백으로 구분하여 출력한다.

$N = 3$ 일 때 $[3, 1, 2, 1, 3, 2]$ 는 청정수열이다. 이 수열의 점수는 다음과 같이 계산된다.

두 $1$ 사이의 수는 $[1, 2, 1]$ 이므로 $(1+2+1) × 1$ 을 점수에 더한다.

두 $2$ 사이의 수는 $[2, 1, 3, 2]$ 이므로 $(2+1+3+2) × 2$ 를 점수에 더한다.

두 $3$ 사이의 수는 $[3, 1, 2, 1, 3]$ 이므로 $(3+1+2+1+3) × 3$ 을 점수에 더한다.

따라서 점수는 $4+16+30$ 으로 $50$ 이다.