lru_cache & Performance

Lab Python Advanced 30 points

Count the number of ways to climb n stairs taking 1, 2 or 3 steps at a time. Use a recursive function with @functools.cache. Print the answer modulo 1,000,000,007.

Input

One integer up to 60.

Output

One integer.

Example

Input

Output

Sample input available Sample output available

Editor

Python

Hints

ways(n) = ways(n-1) + ways(n-2) + ways(n-3).

Without caching this is exponential.

Solution explanation

functools.cache (Python 3.9+) is an unbounded lru_cache.

Show solution

import functools

MOD = 1_000_000_007


@functools.cache
def ways(n):
    if n < 0:
        return 0
    if n == 0:
        return 1
    return (ways(n - 1) + ways(n - 2) + ways(n - 3)) % MOD


print(ways(int(input())))

Output

Answer