<?php


class Solution
{
    public $map;

    /**
     * 三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。

    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/three-steps-problem-lcci
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * @param Integer $n
     * @return Integer
     */
    function waysToStep($n) {


        if($n == 1 || $n == 0){
            return 1;
        }

        if($n == 2){
            return 2;
        }

        if($n == 3){
            return 4;
        }

        if(isset($this->map[$n])){
            return $this->map[$n];
        }

        $first = $this->waysToStep($n - 3) % 1000000007;

        $second = $this->waysToStep($n - 2) % 1000000007;

        $third = $this->waysToStep($n - 1) % 1000000007;

        $this->map[$n] = ($first + $second + $third) % 1000000007;

        return $this->map[$n];
    }


}