Loading...
Loading...
Loading...
A meme is spreading in the hostel WhatsApp group. Kavya notes how many new forwards it gets each day.
On day 0 there are 0 forwards. On day 1 and day 2 there is 1 forward each. From day 3 on, the forwards on a day equal the forwards of the three days before it added together. So the counts go 0, 1, 1, 2, 4, 7, 13 and so on.
Print the number of forwards on day n, modulo 10^9 + 7.
Example 1
Input
6
Output
13
The counts are 0, 1, 1, 2, 4, 7, 13, so day 6 has 13 forwards.
Example 2
Input
25
Output
1389537
The count is still below 10^9 + 7, so it is printed as it is.
Try the problem first. Open one hint at a time.
Let t[i] be the forwards on day i. Every day from 3 on depends only on the three days just before it.
So t[i] = t[i - 1] + t[i - 2] + t[i - 3], with t[0] = 0, t[1] = 1 and t[2] = 1.
Make the table at least 3 cells long so the starting values fit even when n is 0 or 1.
Take the remainder after each sum, and add in long so three values near 10^9 cannot overflow.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor