题目描述
"一步两步, 一步两步， 一步一步似爪牙, 似魔鬼的步伐···"这首滑板星的民谣， 刻画着滑板星人的步伐。不过新一代的滑板星的人进化出了,每次可以走三步的强大功能。我们设现在有一条无限长的笔直道路，滑板星人yzj从0号位置出发, 想要前往n号位置, 请问在他每次走1至3步的前提下, 到达n号点的方案数。
输入
一个n， 代表目的地距起点的距离。(1 ≤ n ≤ 1000000)
输出
输出从起点0到目的地的方法数， 这个答案可能很大， 请对1e8 + 7取模。
提示
13种方案分别为:
1 1 1 1 1
1 1 1 2
1 1 2 1
1 2 1 1
2 1 1 1
1 1 3
1 3 1
3 1 1
2 1 2
1 2 2
2 2 1
2 3
3 2