You climb n stairs taking 1, 2 or 3 steps at a time. In how many different ways can you reach the top? Print the answer modulo 1,000,000,007.
Input
One number n (1 ≤ n ≤ 100,000).
Output
The number of ways, modulo 1,000,000,007.
Examples
Example 1 · Input
4
Expected output
7
Example 2 · Input
1
Expected output
1
Hints
Hint 1
ways[0] = 1; ways[i] = ways[i-1] + ways[i-2] + ways[i-3] (where those exist).
Hint 2
Take % 1000000007 after every addition.
Solution
Show one correct solution (try it yourself first)
#include <iostream>
#include <vector>
using namespace std;
int main() {
const long long MOD = 1000000007;
int n;
cin >> n;
vector<long long> ways(n + 1, 0);
ways[0] = 1;
for (int i = 1; i <= n; i++) {
for (int step = 1; step <= 3; step++)
if (i - step >= 0) ways[i] = (ways[i] + ways[i - step]) % MOD;
}
cout << ways[n] << "\n";
return 0;
}