class Solution:
    def sumOfPower(self, nums: List[int], k: int) -> int:
        MOD = int(1e9 + 7)
        import functools
        @functools.lru_cache(None)
        def f(i, s, l):
            # print((i,s,l))
            if i == 0:
                if s == 0 and l == 0:
                    return 1
                return 0
            v = nums[i - 1]
            res = 0
            # select
            if s - v >= 0 and l - 1 >= 0:
                res += f(i - 1, s - v, l - 1)
            # not
            res += f(i - 1, s, l)
            res %= MOD
            return res

        n = len(nums)
        # dp = [[0 for _ in range(k + 1)] for _ in range(n + 1)]
        # dp[0][0] = 1
        # for i in range(n):
        #     v = nums[i]
        #     for l in range(n, 0, -1):
        #         for s in range(k, 0, -1):
        #             if s - v >= 0:
        #                 dp[l][s] += dp[l - 1][s - v]
        # p = 1
        # ans = 0
        # for l in range(len(nums), 0, -1):
        #     count = dp[l][k]
        #     ans += count * p
        #     p *= 2
        #     p %= MOD
        #     ans %= MOD
        # return ans
        #
        # n = len(nums)
        p = 1
        ans = 0
        for l in range(len(nums), 0, -1):
            count = f(n, k, l)
            ans += count * p
            p *= 2
            p %= MOD
            ans %= MOD
        f.cache_clear()
        return ans