C++ pow2 +DP  taken & not taken|| 7ms
Intuition\n Describe your first thoughts on how to solve this problem. \nRecursive DP take & not take.\nIf a subsequence of length i with sum=k is obtained, the
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nRecursive DP take & not take.\nIf a subsequence of length i with sum=k is obtained, the other positions $n-i$ can be taken or not taken, i.e. a factor $2^{n-i}$.\nThe computation of $2^{n-i}\\pmod{10^9+7}$ uses two functions `pow2` & `powMod` where `powMod` uses a recursive algorithm of least significant bit first algorithm. The function `pow2` uses the fact $2^{29}<p=10^9+7$ & let $exp=30q+r, B=2^{30}\\pmod{p}$ one has\n$$\n2^{exp}\\pmod{p}= (2^{30})^q(2^r)\\pmod{p}=B^q\n\\times (2^r)\\pmod{p}$$\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```\n#pragma GCC optimize("O3", "unroll-loops")\nclass Solution {\npublic:\n    const long long mod=1e9+7; \n    int n, k;\n    int dp[101][101];//dp[i][k]=# of subseq in nums[0..i] with sum=k\n    int f(int i, int k, vector<int>& nums){\n        if (k == 0) return pow2(n-i);\n        if (i>=n || k<0 ) return 0;\n        if (dp[i][k]!=-1) return dp[i][k];\n        long long  ans=2LL*f(i+1, k, nums)%mod;// not take nums[i]\n        if (k>=nums[i]) // take nums[j]\n            ans=(ans+f(i+1, k-nums[i], nums))%mod;\n        return dp[i][k]=ans;\n    }\n    int powMod(long long B, int exp){\n        if (exp==0) return 1;\n        long long y=(exp&1)?B:1;\n        return powMod(B*B%mod, exp/2)*y%mod;\n    }\n    int pow2(int exp){ \n        if (exp<30) return (1<<exp);\n        auto [q, r]=div(exp, 30);\n        long long B=(1<<30)-mod;\n        return powMod(B, q)*(1LL<<r)%mod;\n    }\n    int sumOfPower(vector<int>& nums, int k) {\n        n=nums.size();\n        this->k=k;\n        memset(dp, -1, sizeof(dp));\n        return f(0, k, nums);\n    }\n};\n\n\n\nauto init = []() {\n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n```
['Dynamic Programming', 'C++']