现在小图站在楼下，他想要上楼，每次只能向上跨1-3个台阶，问他从第0个台阶走到第n个台阶有多少种不同的走法？
如图所示：

一个数n（n<=1000000）

一个数，表示走到第n个台阶的走法有多少种？（由于数据比较大，答案对10009取模）