재우의 카드깡

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

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

“신규 이벤트 카드 팩은 서로 다른 $N$종류의 카드가 각각 2장씩, 총 $2N$장의 카드로 구성되어 있습니다. 다만 구매 즉시 $2N$장의 카드를 한꺼번에 획득하는 것은 아닙니다. 이 $2N$개의 카드는 무작위로 섞여 구분할 수 없는 상태로 뒤집혀 있으며, 1EP(이벤트 포인트)를 소모해 뒤집힌 카드 중 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)$에 구할 수 있다.