떡파이어

떡파이어가 늙지 않는 비결은 떡국이다.

떡파이어는 떡국을 먹은 그릇 수만큼 나이를 먹는다. 먹는 즉시 소화가 끝나기 때문에 하루에 원하는 만큼 떡국을 먹을 수 있다. 그러나 전에 얼마나 먹었든, 떡국을 하루라도 먹지 않으면 그날로 생을 마감한다.

떡파이어의 나이는 0세에서 시작하고, 하루가 끝날 때마다 그날 먹은 그릇 수만큼 늘어난다. 디디는 $N$세로 생을 마감한 떡파이어가 나이를 어떻게 먹어 왔는지, 그 과정의 가짓수를 세려고 한다. 산 날수가 다르거나 어느 하루에 먹은 그릇 수가 다르면 서로 다른 과정이다.

$N$이 3이면 과정은 다음 네 가지다.

• 첫째 날 3그릇, 둘째 날 0그릇
• 첫째 날 1그릇, 둘째 날 2그릇, 셋째 날 0그릇
• 첫째 날 2그릇, 둘째 날 1그릇, 셋째 날 0그릇
• 첫째 날 1그릇, 둘째 날 1그릇, 셋째 날 1그릇, 넷째 날 0그릇

$N$이 커지면 가짓수도 매우 많아진다. $N$세로 생을 마감한 떡파이어가 나이를 먹는 과정의 가짓수를 세는 프로그램을 작성하시오.

첫째 줄에 정수 $N$이 주어진다. ($0 \le N \le 10^{12}$)

첫째 줄에 나이를 먹는 과정의 가짓수를 $10^9 + 7$로 나눈 나머지를 출력한다.