수 $n$이 주어집니다. 여러분의 과제는 모든 삼각형 수열의 개수를 세어 그 값을 $10^9 + 7$로 나눈 나머지를 출력하는 것입니다. 수열이 다음 조건을 만족하면 삼각형 수열이라고 부릅니다:

• 수열의 길이는 $n$을 초과하지 않습니다.
• 각 원소는 구간 $[1, n]$에 속하는 정수입니다.
• 이 수열의 어떤 세 원소가 비퇴화 삼각형*의 세 변의 길이가 될 수 있습니다.

$n = 100$일 때 삼각형 수열의 예로는 $(1, 1, 1)$과 $(16, 1, 11, 25, 100)$이 있습니다. 첫 번째 수열에서 비퇴화 삼각형의 세 변은 $(1, 1, 1)$이고, 두 번째 수열에서는 $(16, 11, 25)$입니다.

수열 $(16, 1, 11, 84, 100)$은 어떤 세 원소도 비퇴화 삼각형의 세 변을 이루지 못하므로 삼각형 수열이 아닙니다. 수열 $(5, 5)$ 또한 삼각형 수열이 아닙니다.

* 삼각형의 넓이가 양수일 때 비퇴화 삼각형이라고 합니다. 동치로, 세 꼭짓점이 한 직선 위에 있지 않습니다.

입력

유일한 줄에 정수 $n$ ($3 \le n \le 200\,000$)이 주어집니다.

출력

삼각형 수열의 개수를 $10^9 + 7$(즉, $1000000007$)로 나눈 나머지를 나타내는 정수 하나를 출력합니다.

예제

입력 1

3

출력 1

15

입력 2

4

출력 2

254

노트

$n = 3$일 때 삼각형 수열은 $15$개 있습니다: $(1,1,1), (1,2,2), (1,3,3), (2,1,2), (2,2,1), (2,2,2), (2,2,3), (2,3,2), (2,3,3), (3,1,3), (3,2,2), (3,2,3), (3,3,1), (3,3,2), (3,3,3)$.

$n = 4$일 때 삼각형 수열은 $254$개 있습니다: $(1,1,1), (1,1,1,1), (1,1,1,2), (1,1,1,3), (1,1,1,4), (1,1,2,1), \dots, (4,4,2,4), (4,4,3), (4,4,3,1), (4,4,3,2), (4,4,3,3), (4,4,3,4), (4,4,4), (4,4,4,1), (4,4,4,2), (4,4,4,3), (4,4,4,4)$.