Dynamic Programming
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: $$O(n^2.k)$$ \n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n^2.k)$$ \n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n\nclass Solution {\npublic:\n    long power(long long x, unsigned int y, int p) \n    { \n        long long res = 1; \n        x = x % p;\n    \n        if (x == 0) return 0; \n    \n        while (y > 0) \n        { \n            if (y & 1) \n                res = (res*x) % p; \n    \n            y = y>>1; \n            x = (x*x) % p; \n        } \n        return res%p; \n    } \n    \n    long long sumOfPower(vector<int>& nums, long long k) {\n        long long n = nums.size();\n        vector<vector<vector<long long>>> dp(n + 1, vector<vector<long long>>(n, vector<long long>(k + 1,-1)));\n        long long mod = 1e9 + 7;\n        long long ans = 0;\n\n        for (long long i = 0; i <= n;i++){\n            solve(i,n-1,k,dp,nums);\n            ans += dp[i][n - 1][k] * power(2, n - i, mod);\n            ans %= mod;\n        }\n\n        return ans;\n    }\n    long long solve(long long n,long long i, long long k, auto& dp, vector<int>& nums){\n        if(n>(i+1))\n            return 0;\n\n        if(n==0 && k==0) //base case\n            return 1;\n        \n        if(k<0 || i<0 || n<0)\n            return 0;\n\n        if(dp[n][i][k]!=-1)\n            return dp[n][i][k];\n\n        long long op1 = solve(n - 1, i - 1, k - nums[i], dp, nums);  //include\n        long long op2 = solve(n, i - 1, k , dp, nums);  //exclude\n\n        dp[n][i][k] = ((op1 != -1) ? op1 : 0);\n        dp[n][i][k] += ((op2 != -1) ? op2 : 0);\n\n        long long mod=1e9+7;\n        dp[n][i][k] %= mod;\n\n        return dp[n][i][k];\n    }\n};\n\n\n\n\n\n\n\n\n```
['Dynamic Programming', 'C++']