title
给你一个正整数数组 nums 和一个整数 k 。
分区 的定义是：将数组划分成两个有序的 组 ，并满足每个元素 恰好 存在于 某一个 组中。如果分区中每个组的元素和都大于等于 k ，则认为分区是一个好分区。
返回 不同 的好分区的数目。由于答案可能很大，请返回对 109 + 7 取余 后的结果。
如果在两个分区中，存在某个元素 nums[i] 被分在不同的组中，则认为这两个分区不同。
示例 1：
输入：nums = [1,2,3,4], k = 4
输出：6
解释：好分区的情况是 ([1,2,3], [4]), ([1,3], [2,4]), ([1,4], [2,3]), ([2,3], [1,4]), ([2,4], [1,3]) 和 ([4], [1,2,3]) 。
示例 2：
输入：nums = [3,3,3], k = 4
输出：0
解释：数组中不存在好分区。
示例 3：
输入：nums = [6,6], k = 2
输出：2
解释：可以将 nums[0] 放入第一个分区或第二个分区中。
好分区的情况是 ([6], [6]) 和 ([6], [6]) 。
提示：
1 <= nums.length, k <= 10001 <= nums[i] <= 109
solution
参考 考虑计算坏分区的数目，即第一个组或第二个组的元素和小于 kk 的方案数。根据对称性，我们只需要计算第一个组的元素和小于 kk 的方案数，然后乘 22 即可。
因此原问题转换成从 \textit{nums}nums 中选择若干元素，使得元素和小于 kk 的方案数，这可以用 01 背包求解。
MOD = int(1e9 + 7)
INF = int(1e20)
class Math1:
pass
class Solution:
def countPartitions(self, nums: List[int], k: int) -> int:
# 统计bad数量，总数减去即可。
if sum(nums) < 2*k:return 0
n = len(nums)
dp = [0 for _ in range(k)]
dp[0] = 1
for i, v in enumerate(nums):
for t in range(k-1, 0, -1):
if t >= v:
dp[t] += dp[t - v] % MOD
bad = sum(dp)
return (pow(2, n, MOD) - bad*2 + MOD) % MOD