Count the total number ways to reach the nth stair using step 1, 2 or 3 but the step 3 can be taken only once

ll countWays_(ll n, ll m){
    ll res[n];
    res[0] = 1; res[1] = 1;
    s[0] = 1; s[1] = 2;
    for (ll i=2; i<n; i++)
    {
       if (i <= m)
           res[i] = s[i-1] % MOD;
       else
           res[i] = (s[i-1] - s[i - m - 1] + MOD) % MOD; 
       s[i] = (s[i-1] + res[i]) % MOD;
    }
    return res[n-1];
}

concatenar([], Xs, Xs).
concatenar([X|Xs], Ys, [X|Zs]) :- concatenar(Xs,  Ys, Zs).

?- concatenar([a,b,c], [x,y,z], L).

# Python 3
def fib(n): 
    print(f'Fib: {n}')
    if n <= 1:
        print('End')
        return n
    else:
        print(f'Send: {n-1} and {n-2}')
    return fib(n-1) + fib(n-2) 

def countWays(s): 
    return fib(s + 1) 

s = 4
print("Number of ways = ")
print(countWays(s))

Fib: 5           # A
Send: 4 and 3    # A.B and A.C
Fib: 4           # A.B
Send: 3 and 2    # A.B.1 and A.B.2
Fib: 3           # A.B.1
Send: 2 and 1    # A.B.1.1 and A.B.1.2
Fib: 2           # A.B.1.1
Send: 1 and 0    # A.B.1.1.1 and A.B.1.1.2
Fib: 1           # A.B.1.1.1
End              # (END) A.B.1.1.1       -> 1
Fib: 0           # A.B.1.1.2
End              # (END) A.B.1.1.2       -> 0
Fib: 1           # A.B.1.2
End              # (END) A.B.1.2         -> 1
Fib: 2           # A.B.2
Send: 1 and 0    # A.B.2.1 and A.B.2.2
Fib: 1           # A.B.2.1
End              # (END) A.B.2.1         -> 1
Fib: 0           # A.B.2.2
End              # (END) A.B.2.2         -> 0
Fib: 3           # A.C
Send: 2 and 1    # A.C.1 and A.C.2
Fib: 2           # A.C.1
Send: 1 and 0    # A.C.1.1 and A.C.1.2
Fib: 1           # A.C.1.1
End              # (END) A.C.1.1         -> 1
Fib: 0           # A.C.1.2
End              # (END) A.C.1.2         -> 0
Fib: 1           # A.C.2
End              # (END) A.C.2           -> 1
5                                     # 1 + 0 + 1 + 1 + 0 + 1 + 0 + 1

>>> print(fib(5))
Fib: 5
Send: 4 and 3
Fib: 4
...
Fib: 1
End
5

public static void main(String[] args) {
    int n = 46;
    int [] arr = new int[n+1];
    arr[0] = 1;
    arr[1] = 1;
    arr[2] = 2;
    arr[3] = 4;
    for(int i = 3; i < n; i++){
        arr[i]= arr[i-1]+arr[i-2]+arr[i-3];
    }
    System.out.println(arr[n]);
}