Modified version of KnapSack
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(nnk)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(nnk)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    private static final int MOD = (int)Math.pow(10,9)+7;\n    long[] pow;\n    public int sumOfPower(int[] nums, int k) {\n        int n = nums.length;\n        long[][][] dp = new long[n][k+1][n+1];\n        Arrays.stream(dp).forEach(arr -> Arrays.stream(arr).forEach(v -> Arrays.fill(v, -1)));\n        Arrays.sort(nums);\n        pow = new long[n+1];\n        pow[0] = 1;\n        for(int i=1; i<=n; i++)\n            pow[i] = (pow[i-1]*2)%MOD;\n        return (int)findPower(0,0,n,k,nums,dp);\n    }\n    public long findPower(int i, int cnt, int n, int k, int[] nums, long[][][] dp){\n        if (k == 0)\n            return pow[n-cnt];\n        if (i >= n || k < 0 || nums[i] > k)\n            return 0;\n        if (dp[i][k][cnt] != -1)\n            return dp[i][k][cnt];\n        return dp[i][k][cnt] = (findPower(i+1, cnt+1, n, k-nums[i], nums, dp)%MOD + findPower(i+1, cnt, n, k, nums, dp)%MOD)%MOD;\n    }\n\n    public long modPower(long a, int n){\n        if (n == 0)\n            return 1;\n        if (n == 1)\n            return a%MOD;\n        long power = modPower(((a%MOD)*(a%MOD))%MOD, n/2);\n        return (n&1) > 0 ? ((a%MOD)*(power%MOD))%MOD : power%MOD;\n    }\n}\n```
['Java']