Sequence Recurrence Modulo

Given a sequence \(a\) defined by the recurrence:

\[ a_x = \begin{cases} 1 & \text{if } x \in \{1,2,3\} \\ a_{x-1} + a_{x-3} & \text{if } x \ge 4 \end{cases} \]

Compute the \(n\)th term of the sequence modulo \(10^9+7\).

inputFormat

The input consists of a single integer \(n\) (\(1 \le n \le 10^\text{?}\)), which specifies the term of the sequence to compute.

Input Format: n

outputFormat

Output a single integer representing the \(n\)th term of the sequence modulo \(10^9+7\).

sample

1

1