[Java/C++/Python] DP, O(k) Space
Explanation\n\ndp[i][v] means the number of subsequence of i elements with sum of v.\nFor each value a and each current sum v,\nwe will have dp[i][v] += dp[i - 
# **Explanation**\n\n`dp[i][v]` means the number of subsequence of `i` elements with sum of `v`.\nFor each value `a` and each current sum `v`,\nwe will have `dp[i][v] += dp[i - 1][v - a])`.\n\nFinally for `dp[i][k]`,\nfor each `n - i`  other elements,\nwe can have it in or not in the subsequence,\nso result is `SUM(dp[i][k] * 2 ^(n - i))`\n<br>\n\n# **Complexity**\nTime `O(nnk)`\nSpace `O(nk)`\n<br>\n\n**Java**\n```java\n    public int sumOfPower(int[] A, int k) {\n        int n = A.length, mod = (int)1e9 + 7, res = 0, pow2 = 1;\n        int[][] dp = new int[n + 1][k + 1];\n        dp[0][0] = 1;\n        for (int a : A)\n            for (int v = k; v >= a; --v)\n                for (int i = n; i > 0; --i)\n                    dp[i][v] = (dp[i][v] + dp[i - 1][v - a]) % mod;\n        for (int i = n; i > 0; --i) {\n            res = (int)(res + (1L * pow2 * dp[i][k]) % mod) % mod;\n            pow2 = (pow2 * 2) % mod;\n        }\n        return res;\n    }\n```\n**C++**\n```cpp\n    int sumOfPower(vector<int>& A, int k) {\n        int n = A.size(), mod = 1e9 + 7, res = 0, pow2 = 1;\n        vector<vector<int>> dp(n + 1, vector<int>(k + 1));\n        dp[0][0] = 1;\n        for (int& a : A)\n            for (int v = k; v >= a; --v)\n                for (int i = n; i > 0; --i)\n                    dp[i][v] = (dp[i][v] + dp[i - 1][v - a]) % mod;\n        for (int i = n; i > 0; --i) {\n            res = (res + (1L * pow2 * dp[i][k]) % mod) % mod;\n            pow2 = (pow2 * 2) % mod;\n        }\n        return res;\n    }\n```\n\n**Python**\n```py\n    def sumOfPower(self, A: List[int], k: int) -> int:\n        n = len(A)\n        mod = 10 ** 9 + 7\n        dp = [[0] * (k + 1) for i in range(n + 1)]\n        dp[0][0] = 1\n        for a in A:\n            for v in range(k, a - 1, -1):\n                for i in range(n, 0, -1):\n                    dp[i][v] = (dp[i][v] + dp[i - 1][v - a]) % mod\n        return sum(pow(2, n - i, mod) * dp[i][k] for i in range(1, n + 1)) % mod\n```\n<br>\n\n# **Solution II**\nIn the first solution,\nwe count the number of element in sum,\nthen caculate pow of 2 for other in the end.\nThis idea mixed up some math and dp.\n\nInspired from @stanislav-iablokov \'s dfs [solution](https://leetcode.com/problems/find-the-sum-of-the-power-of-all-subsequences/discuss/4884094/PythonRust-Knapsack).\napply the Chinese QinJiuShao algoritme(\u79E6\u4E5D\u97F6\u7B97\u6CD5), also known as Horner\'s method.\n\n\nActually we can calculate the pow of 2 during the dp addition.\nso the we don\'t need to count the number and can save the first dimension.\nFor each element `a`,\nwe can choose take it or not.\n`dp[v] = dp[v] + d[v] + dp[v - a]`\n\n`dp[v]` for the sequence not taking it,\n`dp[v] + dp[v - a]` for the sequence taking it.\n\n\n# **Complexity**\nTime `O(nk)`\nSpace `O(nk)`\n<br>\n\n**Java**\n```java\n    public int sumOfPower(int[] A, int k) {\n        int n = A.length, mod = (int)1e9 + 7;\n        int[] dp = new int[k + 1];\n        dp[0] = 1;\n        for (int a : A)\n            for (int v = k; v >= 0; --v)\n                dp[v] = (dp[v] * 2 % mod + (v >= a ? dp[v - a] : 0)) % mod;\n        return dp[k];\n    }\n```\n**C++**\n```cpp\n    int sumOfPower(vector<int>& A, int k) {\n        int n = A.size(), mod = 1e9 + 7;\n        vector<int> dp(k + 1);\n        dp[0] = 1;\n        for (int& a : A)\n            for (int v = k; v >= 0; --v)\n                dp[v] = (dp[v] * 2 % mod + (v >= a ? dp[v - a] : 0)) % mod;\n        return dp[k];\n    }\n```\n\n**Python**\n```py\n    def sumOfPower(self, A: List[int], k: int) -> int:\n        n = len(A)\n        mod = 10 ** 9 + 7\n        dp = [1] + [0] * k\n        for a in A:\n            for v in range(k, -1, -1):\n                dp[v] = (dp[v] * 2 + (dp[v - a] if v >= a else 0)) % mod\n        return dp[k]\n```\n
['C', 'Python', 'Java']