Batch growth: hints, no solution

A bakery's sourdough starter produces batches whose sizes follow a rule. The sizes on days 1, 2 and 3 are given. From day 4 onwards, each day's batch equals the sum of the batches of the three previous days. Given a day number and the first three sizes, return the size of the batch on that day. The answer can be huge, so return it modulo 1000000007. Days are numbered from 1.

Examples

Input

day = 6, first = 1, second = 1, third = 2

Output

13

Note

The sizes are 1, 1, 2, 4, 7, 13.

Input

day = 2, first = 5, second = 7, third = 9

Output

7

Note

Day 2 is one of the given sizes.

Input

day = 10, first = 0, second = 0, third = 1

Output

44

Constraints

• 1 <= day <= 1000000
• 0 <= first, second, third <= 1000000000

Hint 1: a nudge

What do you need to know about earlier days to work out one new day? Does the answer for day 50 need anything from day 1 directly?

Unlock the full hints and timed practice with a pass

The second and third hints and the timed, runner-checked practice are part of a pass.

See pricing