Fast with prefilter to shrink the input size
Intuition\nPrefilter to shrink the input size\n\n# C++ Code\n\nclass Solution {\npublic:\n    static int shorten(long long input) {\n        return input % (100
# Intuition\nPrefilter to shrink the input size\n\n# C++ Code\n```\nclass Solution {\npublic:\n    static int shorten(long long input) {\n        return input % (1000000000L + 7);\n    }\n\n    int sumOfPower(vector<int> &inputValues, int k) {\n        vector<int> nums;\n        long long ignored = 1;\n        for (int u: inputValues) {\n            if (u <= k) {\n                nums.push_back(u);\n            } else {\n                ignored = shorten(ignored *2);\n            }\n        }\n        if (nums.empty()) {\n            return 0;\n        }\n\n        long* past = (long*)calloc((k + 1), sizeof(long));\n        long* current = (long*)calloc((k + 1), sizeof(long));\n\n        past[0] = 2;\n        past[nums[0]] = 1;\n        for (int u = 1; u < nums.size(); u++) {\n            for (int sum = 0; sum <= k; sum++) {\n                int value = nums[u];\n                long long newValue = sum >= value ? past[sum - value] : 0;\n                current[sum] = shorten(newValue + past[sum] * 2);\n            }\n            long* tmp = past;\n            past = current;\n            current = tmp;\n        }\n        long long value = past[k];\n        free(past);\n        free(current);\n        return shorten(value * ignored);\n    }\n};\n```\n\n\n# Java Code\n```\nclass Solution {\n    static long shorten(long input) {\n        return input % (1000000000L + 7);\n    }\n\n    public int sumOfPower(int[] inputValues, int k) {\n        int count = 0;\n        for (int u = 0; u < inputValues.length; u++) {\n            count += inputValues[u] <= k ? 1 : 0;\n        }\n        if (count == 0) {\n            return 0;\n        }\n        int ignored = inputValues.length - count;\n\n        int nums[] = new int[count];\n        int inc = 0;\n        for (int u = 0; u < inputValues.length; u++) {\n            if (inputValues[u] <= k) {\n                nums[inc++] = inputValues[u];\n            }\n        }\n\n        long dp[][] = new long[k + 1][nums.length];\n        dp[0][0] = 2;\n        for (int u = 1; u < nums.length; u++) {\n            dp[0][u] = shorten(2L * dp[0][u - 1]);\n        }\n        dp[nums[0]][0] = 1;\n        for (int k1 = 1; k1 <= k; k1++) {\n            for (int n1 = 1; n1 < nums.length; n1++) {\n                int value = nums[n1];\n                if (k1 - value >= 0) {\n                    dp[k1][n1] += dp[k1 - value][n1 - 1];\n                }\n                dp[k1][n1] = shorten(dp[k1][n1] + dp[k1][n1 - 1] * 2);\n            }\n        }\n        long value = dp[k][nums.length - 1];\n        for (int k1 = 0; k1 < ignored; k1++) {\n            value = shorten(value * 2);\n        }\n        return (int)value;\n    }\n}\n\n```
['C++', 'Java']