2 ^ (n - i)
When we find cnt elements that sum to k, those elements appear in 2 ^ (n - cnt) subsequences.\n\nSo, we can run 3D DP (i, cnt, sum) to find such elements and co
When we find `cnt` elements that sum to `k`, those elements appear in `2 ^ (n - cnt)` subsequences.\n\nSo, we can run 3D DP (i, cnt, sum) to find such elements and count subsequences.\n\nWe can further simplify this to 2D (thanks to [stanislav-iablokov](https://leetcode.com/stanislav-iablokov/)) by doing `2 ^ (n - i)` and multiplying the result by `2` when we *skip* an element.\n\nBoth formulas are equivalent if you think about it. Say `n` is 10, and we picked 3 elements and skipped 4 (therefore `i == 7`):\n- `2 ^ (10 - 3)`\n- `2 ^ 4 * 2 ^ (10 - 7)`\n\t- The result is the same (128) for both formulas.\n\n**Complexity Analysis**\n- 3D DP solution has a cubic time/memory complexity O(n * n * k), and it is accepted due to generous constraints.\n- After simplifying DP from 3D to 2D, the time and memory complexity becomes quadratic O(n * k).\n\t- The memory optimization for the bottom-up solution reduced the memory complexity to O(k).\n\n**Python 3**\n```python\nclass Solution:\n    def sumOfPower(self, nums: List[int], k: int) -> int:\n        @cache\n        def dfs(i: int, sum: int) -> int:\n            if sum == k:\n                return pow(2, len(nums) - i, 1000000007)\n            if sum > k or i >= len(nums):\n                return 0\n            return (2 * dfs(i + 1, sum) + dfs(i + 1, sum + nums[i])) % 1000000007\n        return dfs(0, 0)\n```\n**C++ Bottom-Up**\nIdea by [lee215](https://leetcode.com/lee215/).\n```cpp\nint sumOfPower(vector<int>& nums, int k) {\n    int dp[101] = { 1 }, mod = 1000000007;\n    for (int n : nums)\n        for (int sum = k; sum >= 0; sum -= 1)\n            dp[sum] = (2LL * dp[sum] + (sum >= n ? dp[sum - n] : 0)) % mod;\n    return dp[k];\n}\n```\n**C++ Top-Down**\n```cpp\nint dp[101][101] = {}, mod = 1000000007;\nint modPow(int x, unsigned int y, unsigned int m)\n{\n    if (y == 0)\n        return 1;\n    long p = modPow(x, y / 2, m) % m;\n    p = (p * p) % m;\n    return y % 2 ? (p * x) % m : p;\n}\nlong long dfs(int i, int k, vector<int> &nums) {\n    if (k == 0)\n        return modPow(2, nums.size() - i, mod);\n    if (k < 0 || i >= nums.size())\n        return 0;\n    if (dp[i][k] == 0)\n        dp[i][k] = (1LL + 2 * dfs(i + 1, k, nums) + dfs(i + 1, k - nums[i], nums)) % mod;\n    return dp[i][k] - 1;\n}\nint sumOfPower(vector<int>& nums, int k) {\n    return dfs(0, k, nums);\n}\n```
['C', 'Python3']