楼梯有n阶，可以一步上一阶、两阶或三阶，问有多少种不同的走法

用C语言
楼梯有n阶，可以一步上一阶、两阶或三阶，问有多少种不同的走法
由于答案很大，mod(1e9+7)输出
输入数据
一个正整数n，代表楼梯的阶数，n<=1000000
输出数据
方案数
样例输入
3
样例输出
4

#include<stdio.h>
#include<stdlib.h>
int countWays (int n)
{if (n<=0)
   return 0;
if (n==1)
   return 1;
else if(n==2)
   return 2;
else if(n==3)
   return 4;
else
  {
  return countWays(n-1)+countWays(n-2)+countWays(n-3);
 }
}   
 
void main()
{
    int n;
    scanf("%d",&n);
    int f = countWays(n);
    printf("有%d种方法\n",f);
}