시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 37 28 26 76.471%

문제

영희는 지난주에 철수의 생일 선물로 서로 다른 맛의 사탕 N개를 준비했습니다. 사탕은 맛에 따라 1번부터 N번까지의 사탕이 있다고 하겠습니다. 사탕들을 모두 상자에 담아서 정성스럽게 포장을 하여 철수에게 전해주기로 하였습니다.

철수의 생일 날이 되었습니다. 영희는 준비해두었던 사탕 꾸러미를 철수에게 주었습니다. 그런데 철수는 꾸러미에서 이상한 점을 발견했습니다. 이미 포장이 뜯어져 있던 것입니다. 철수는 영희에게 원래 받았어야 할 사탕의 개수 N에 대해 전해 들었고, 사탕이 몇 개 사라졌을 수도 있겠다는 생각이 들었습니다. 사탕은 하나도 사라지지 않았을 수 있고, 전부 다 사라졌을 수도 있습니다.

철수는 K(1≤K≤N)개의 사탕을 받으면 총 2K만큼의 만족도를 느낀다고 합니다. 예를 들어, 철수가 1번, 3번, 4번 총 3개의 사탕을 선물 받았다면, 23만큼의 만족도를 느끼게 되는 것입니다. 단, 철수가 사탕을 하나도 못 받는 경우에는 철수는 0의 만족도를 느낍니다.

이때, 철수는 본인이 얻을 수 있는 가능한 모든 경우의 수의 만족도 합이 궁금해졌습니다. 철수의 궁금증을 해결해주는 프로그램을 작성하세요.

입력

입력의 첫째 줄에는 서로 다른 사탕의 개수를 나타내는 N(2≤N≤100,000)가 주어집니다.

출력

첫째 줄에 철수가 느낄 수 있는 모든 만족도의 합을 1,000,000,007로 나눈 나머지를 출력합니다.

예제 입력 1

2

예제 출력 1

8

힌트

(1번 사탕)을 선물 받는 경우 만족도는 2, (2번 사탕)을 선물 받는 경우 만족도는 2, (1, 2번 사탕)을 선물 받는 경우 만족도는 4.

따라서 2 + 2 + 4 = 8