28693번 - 재우의 카드깡

재우는 축구 게임에 중독되어 있다. 이 게임은 선수를 나타내는 카드를 수집해서 팀을 구성하고, 구성한 팀으로 다른 플레이어와 경기하는 방식으로 진행된다. 특히 이 게임에서는 선수 카드를 강화하여 선수에게 더 높은 능력치를 부여할 수 있는데, 강화를 위해서는 동일한 선수 카드 한 장이 재료로 필요하다. 강화 재료로 소모된 카드는 사라진다. 강한 선수를 만들기 위해서 오늘도 재우는 카드 팩을 열어보기로 했다.

재우는 새로 나온 이벤트 카드 팩에 기존의 $N$개의 카드가 아닌, 그 $2$배인 $2N$개의 카드가 들어있다는 사실을 알게 되었다. 의아했던 재우는 이벤트 공지사항을 읽어보기로 했다. 내용은 다음과 같다.

“신규 이벤트 카드 팩은 서로 다른 $N$종류의 카드가 각각 $2$장씩 총 $2N$장의 카드로 구성되어 있습니다. 다만, 구매 즉시 $2N$장의 카드를 한꺼번에 획득하는 것은 아닙니다. 해당 $2N$개의 카드는 무작위로 섞여 구분할 수 없는 상태로 뒤집혀 있으며, $1$EP(이벤트 포인트)를 소모해서 뒤집힌 카드들 중 $2$개를 골라서 확인할 수 있습니다. 두 장의 카드를 동시에 확인하는 방식이 아닌, 한 장의 카드를 골라서 확인한 후 다른 한 장을 고르는 방식입니다. 고른 두 카드가 동일하면, 해당 카드 두 장을 즉시 지급해 드립니다. 고른 두 카드가 다르다면, 해당 카드 $2$개는 다시 뒤집혀 원래 위치로 각각 돌아갑니다.”

EP가 유료로 구매해야 얻을 수 있는 재화라는 것을 깨달은 재우는 게임 회사의 상술에 화가 났지만, 딱 한 팩만 구매한 뒤, 팩 안의 모든 카드를 가져가기 위해 필요한 EP의 기댓값을 구하기로 했다. 재우를 도와 이 값을 구해보도록 하자. 재우는 비상한 기억력을 가지고 있어서 한 번 본 카드의 위치와 종류를 기억한다. 재우는 항상 최적의 방법으로 모든 카드를 가져가려고 한다.

첫째 줄에 카드 쌍의 개수를 나타내는 정수 $N$($1\le N\le 1\,000$)이 주어진다.

$2N$개의 카드가 들어 있는 카드 팩의 모든 카드를 가져가기 위해 필요한 EP의 기댓값을 $10^9+7$로 나눈 나머지를 출력하라. 단, $10^9+7$은 소수이다.

기약분수 $\frac{p}{q}(p\ge 0,q>0,\gcd(p,q) =1)$를 $M$으로 나눈 나머지는 $q^{-1}$가 $q\cdot q^{-1}\equiv 1\pmod M$을 만족하는 정수, 즉 $q$의 $M$에 대한 모듈로 곱셈 역원일 때, $p\cdot q^{-1}\pmod M$로 정의한다. 만약 정수일 경우 $q=q^{-1}=1$이므로 $p\pmod M$를 의미한다. 역원을 구하는 방법은 아래 힌트에 나와 있다.

이 문제의 모든 입력에 대해 정답이 유일하게 결정된다. 즉, 답은 정수이거나 기약분수로 나타냈을 때 분모가 $10^9+7$과 서로소다.

$a$의 $p$에 대한 모듈로 곱셈 역원 $a^{-1}$을 구하는 방법은 페르마 소정리를 이용한 방법과 확장 유클리드 호제법을 이용하는 방법 등이 있다. 이중 페르마 소정리를 이용한 방법을 설명하면 다음과 같다. $p$와 서로소인 자연수 $a$에 대하여 페르마 소정리에 의해 $a^{p-1}\equiv 1 \pmod p$가 성립하므로, $a\cdot a^{p-2}\equiv 1 \pmod p$이다. 즉, 서로소인 수에 대해 역원은 유일하므로 $a^{-1}\equiv a^{p-2}\pmod p$이다. $a^{p-2}\bmod p$는 분할정복을 이용한 거듭제곱을 통하여 $\mathcal{O}(\lg p)$에 구할 수 있다.