SP10802 TETRAHRD - Sum of Tetranacci numbers

The sequence of Tetranacci numbers is defined as follows: a $ _{n} $ = a $ _{n-1} $ + a $ _{n-2} $ + a $ _{n-3} $ + a $ _{n-4} $ with a $ _{0} $ = a $ _{1} $ = a $ _{2} $ = 0 and a $ _{3} $ = 1.

Input starts with a positive integer t

Calculate a $ _{m} $ + a $ _{m+1} $ + ... + a $ _{n} $ and print the result modulo 1000000007.