시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB96623879.167%

문제

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로 나눈 나머지를 출력한다.

예제 입력 1

3 1 1 1

예제 출력 1

6

예제 입력 2

3 3 1 1

예제 출력 2

9

예제 입력 3

50 10 10 10

예제 출력 3

0

예제 입력 4

18 12 8 9

예제 출력 4

81451692

예제 입력 5

50 25 25 25

예제 출력 5

198591037

출처