Java + Dp -> TC: O(N*N*K), SC: O(N*K)
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n\n    long mod = 1000000007;\n\n    public long pow(int n){\n        long p = 1;\n        while(n-->0){\n            p *= 2;\n            p %= mod;\n        }\n        return p;\n    }\n\n    public int sumOfPower(int[] nums, int k) {\n        int n = nums.length;\n        // dp[i][j] -> number of subseqences with sum i & length j\n        long[][] dp = new long[k+1][n+1];\n        dp[0][0] = 1;\n        for(int i=0; i<n; i++){\n            long[][] dpNew = new long[k+1][n+1];\n            for(int l=0; l<=n; l++){\n                for(int s=0; s<=k; s++){\n                    // if we consider current element and\n                    // if there are subseqences with sum (s-nums[i]) & length (l-1)\n                    if((s-nums[i])>=0 && (l-1)>=0 && dp[s-nums[i]][l-1]!=0){\n                        dpNew[s][l] += dp[s-nums[i]][l-1];\n                        dpNew[s][l] %= mod;\n                    }\n                    // if we won\'t consider current element\n                    if(dp[s][l]!=0){\n                        dpNew[s][l] += dp[s][l];\n                        dpNew[s][l] %= mod;\n                    }\n                }\n            }\n            dp = dpNew;\n        }\n        long ans = 0;\n        // if there are dp[k][l] subsequences with sum k & length len\n        // then we can make dp[k][len] * (2^(n-len)) subsequences with given power condition\n        // 2^(n-len) -> indicates there are (n-len) elements and\n        // for each element there are two choices -> consider or dont\'t consider in final subsequences\n        for(int l=1; l<=n; l++){\n            ans += pow(n-l)*dp[k][l];\n            ans %= mod;\n        }\n        return (int)ans;\n    }\n}\n```
['Dynamic Programming', 'Java']