O(N * K) Solution | C++
Approach\nFirst lets see how we can find the number of subsequences that have a sum of k. This can be done by using similar logic to a knapsack problem, with a 
# Approach\nFirst lets see how we can find the number of subsequences that have a sum of k. This can be done by using similar logic to a knapsack problem, with a bit of modification. Every time we look at a new element, we can either include it in our current subsequece or not. We can have dp with state $$dp[n][k][2]$$, here what we are doing is that when we get to a new element in the array, we consider both possibilities of including the current element in the sum or not. First column in the $$dp$$ represents the current element, second represents the sum so far and the third represent whether we include the current element in the sum or nowt. This way we can have these transitions processing the array from left to right :- \n\n\n$$dp[i][sum][1] = dp[i - 1][sum - nums[i]][1] + dp[i - 1][sum - nums[i]][0]\n$$\n\n$$dp[i][sum][1] = dp[i - 1][sum][1] + dp[i - 1][sum][0]$$\n\nThe first transition considers the current element in the sum while the second one doesn\'t.\n\n\nNow what we need to do is modify this to calculate all possbile subsequeses, that contain any subsequece represented by $$dp[curElemnt][curSum][taken]$$, comparing this to what we have caculated so far, the only difference here is that every time we don\'t take an element into our sum, we can still include that element in the current subsequence and expand it. \nSo we can modify the second dp transition to something like this \n$dp[i][sum][1]= 2 * (dp[i\u22121][sum][1]+dp[i\u22121][sum][0])$\n\nAnd the solution then becomes \n\n$$ dp[n][k][0] + do[n][k][1] $$\n\n\n# Complexity\n- Time complexity:\n $$O(nk)$$ \n\n- Space complexity:\n $$O(nk)$$ \n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int sumOfPower(vector<int>& a, int k) {\n        int n = a.size(), mod = 1000000007, res = 0;\n        int dp[n + 1][k + 1][2];\n        memset(dp, 0, sizeof(dp));\n        dp[0][0][0] = 1;\n        for(int i = 1; i <= n; i++) {\n            for(int sum = 0; sum <= k; sum++) {\n                if(a[i - 1] <= sum)\n                    dp[i][sum][1] += (dp[i - 1][sum - a[i - 1]][0] + dp[i - 1][sum - a[i - 1]][1]) % mod;\n                dp[i][sum][0] += 2ll * (dp[i - 1][sum][0] + dp[i - 1][sum][1]) % mod;\n                dp[i][sum][0] %= mod;\n                dp[i][sum][1] %= mod;\n            }\n            \n        }\n        res = (res + dp[n][k][0] + dp[n][k][1]) % mod;\n\n        return res;\n    }\n};\n```
['C++']