from functools import lru_cache
class Solution:
    def numOfArrays(self, n: int, m: int, k: int) -> int:
        if k>m:
            return 0
        @lru_cache
        def sol(i,ct,curr):
            if i==n:
                if ct==k and curr<=m:
                    return 1
                return 0
 
            if ct>k or curr>m:
                return 0
 
 
            t1=sol(i+1,ct+1,curr+1)
            t2=sol(i,ct,curr+1)
            if i!=0:
                t3=sol(i+1,ct,curr)
            else:
                t3=0
 
            return (t1+t2+t3)%(10**9+7)
        return sol(0,0,0)

ZnJvbSBmdW5jdG9vbHMgaW1wb3J0IGxydV9jYWNoZQpjbGFzcyBTb2x1dGlvbjoKICAgIGRlZiBudW1PZkFycmF5cyhzZWxmLCBuOiBpbnQsIG06IGludCwgazogaW50KSAtPiBpbnQ6CiAgICAgICAgaWYgaz5tOgogICAgICAgICAgICByZXR1cm4gMAogICAgICAgIEBscnVfY2FjaGUKICAgICAgICBkZWYgc29sKGksY3QsY3Vycik6CiAgICAgICAgICAgIGlmIGk9PW46CiAgICAgICAgICAgICAgICBpZiBjdD09ayBhbmQgY3Vycjw9bToKICAgICAgICAgICAgICAgICAgICByZXR1cm4gMQogICAgICAgICAgICAgICAgcmV0dXJuIDAKCiAgICAgICAgICAgIGlmIGN0Pmsgb3IgY3Vycj5tOgogICAgICAgICAgICAgICAgcmV0dXJuIDAKCiAgICAgICAgICAgIAogICAgICAgICAgICB0MT1zb2woaSsxLGN0KzEsY3VycisxKQogICAgICAgICAgICB0Mj1zb2woaSxjdCxjdXJyKzEpCiAgICAgICAgICAgIGlmIGkhPTA6CiAgICAgICAgICAgICAgICB0Mz1zb2woaSsxLGN0LGN1cnIpCiAgICAgICAgICAgIGVsc2U6CiAgICAgICAgICAgICAgICB0Mz0wCiAgICAgICAgICAgIAogICAgICAgICAgICByZXR1cm4gKHQxK3QyK3QzKSUoMTAqKjkrNykKICAgICAgICByZXR1cm4gc29sKDAsMCwwKQ==