Can anyone help me in this question. It was asked in one of my interview 3-4 months ago and i still don’t know the answer.

A box contain a number of chocolates that can only be removed 1 at a time or 3 at a time. How many ways can the box be emptied? The answer can be very large so return it modulo of 10^9+7.

for ex. n=7 chocolates initially they can be removed nine ways as follow:

(1,1,1,1,1,1,1)

(1,1,1,1,3)

(1,1,1,3,1)

(1,1,3,1,1)

(1,3,1,1,1)

(3,1,1,1,1)

(1,3,3)

(3,1,3)

(3,3,1)

1<=n<=10^9

Time limit 1 sec.

Input : n

output : as asked in question

Note : beware of limits of n