#2759 Candy

12  1 s   128 MB  

Description

 영희는 지난 주에 철수의 생일 선물로 서로 다른 맛의 사탕 N 개를 준비했다. 사탕은 맛에 따라 1 번부터 N번 까지의 사탕으로 분류된다. 영희는 철수에게 주기 위하여 사탕들을 모두 상자에 담아 정성스럽게 포장하였다.  
 철수의 생일 날, 영희는 준비해두었던 사탕 꾸러미를 철수에게 줬다. 그런데 철수는 꾸러미에서 이상한 점을 발견했다. 몇 개의 사탕이 이미 포장이 뜯어져 있었다! 철수는 영희에게 물어 원래 들어있던 사탕의 개수는 N개 라는 사실을 알게되었다. 사탕은 하나도 사라지지 않았을 수도 있고, 전부다 사라졌을 수도 있다.  
 철수는 K(1 ≤ K ≤ N)개의 사탕을 선물 받으면 총 2k만큼의 만족도를 얻는다. 예를 들어서 철수가 1, 3, 4 번 사탕을 선물 받았다면, 8 의 만족도를 느끼게 된다. 단, 철수가 사탕을 하나도 못 받는 경우에는 철수는 0 의 만족도를 느끼게 된다. 
 이 때, 철수가 사탕 꾸러미를 통해 사탕들을 얻을 수 있는 모든 경우의 수에 대하여 각 경우에 얻을 수 있는 만족도의 합은 얼마일까? 철수의 궁금증을 풀어주기 위하여 이를 계산해주자.

Input

입력의 첫 줄에 서로 다른 사탕의 개수를 나타내는 정수 N이 주어진다. N은 2와 105사이의 정수이다.

Output

첫 줄에 철수가 사탕을 받을 수 있는 모든 경우의 수에 대해 만족도들의 합을 1,000,000,007 로 나눈 나머지를 출력한다. 

Sample Input

Sample Output

2
8

Source

shake 2016! 본선