13007번 - ntopia

BOJ 알고리즘 캠프에 강사로 참여하고 있는 dotorya, kesakiyo, hongjun7은 301호에서 도원결의를 맺고 프로젝트 아이돌 그룹 ntopia을 결성했다. 

ntopia의 데뷔 앨범에는 총 S개의 곡이 수록될 예정이다. 각각의 곡은 세 사람중 적어도 한 명이 불러야 한다. 즉, 어떤 곡은 두 사람이 불러도 되고, 세 사람이 모두 함께 불러도 된다.

세 사람이 녹음해야 하는 곡의 수가 주어질 때, 앨범을 만들 수 있는 방법의 수를 구하는 프로그램을 작성하시오.

두 앨범 A와 B가 있을 때, 참여한 사람이 다른 곡이 존재한다면, 두 앨범은 다른 앨범이라고 한다. 

첫째 줄에 앨범에 포함된 곡의 개수 S와 dotorya, kesakiyo, hongjun7이 불러야 하는 곡의 수가 주어진다. (1 ≤ S ≤ 1,000,000, 1 ≤ dotorya, kesakiyo, hongjun7 ≤ S)

첫째 줄에 앨범을 만들 수 있는 방법의 수를 1,000,000,007로 나눈 나머지를 출력한다.