12:17 (UTC): The sample input 1 and 2 were swapped. The error is now fixed. We are very…
- User
12:17 (UTC): The sample input 1 and 2 were swapped. The error is now fixed. We are very sorry for your inconvenience.
There are N children in AtCoder Kindergarten, conveniently numbered 1 through N. Mr. Evi will distribute C indistinguishable candies to the children.
If child i is given a candies, the child's happiness will become x_i^a, where x_i is the child's excitement level. The activity level of the kindergarten is the product of the happiness of all the N children.
For each possible way to distribute C candies to the children by giving zero or more candies to each child, calculate the activity level of the kindergarten. Then, calculate the sum over all possible way to distribute C candies. This sum can be seen as a function of the children's excitement levels x_1,..,x_N, thus we call it f(x_1,..,x_N).
You are given integers A_i,B_i (1≦i≦N). Find modulo 10^9+7.
Constraints
- 1≦N≦400
- 1≦C≦400
- 1≦A_i≦B_i≦400 (1≦i≦N)
Input
The input is given from Standard Input in the following format:
N C A_1 A_2 ... A_N B_1 B_2 ... B_N
Output
Print the value of modulo 10^9+7.
Examples
Input
2 3 1 1 1 1
Output
4
Input
1 2 1 3
Output
14
Input
2 3 1 1 2 2
Output
66
Input
4 8 3 1 4 1 3 1 4 1
Output
421749
Input
3 100 7 6 5 9 9 9
Output
139123417
Assistant
We are given:
N children, each child i has an "excitement level" x_i, but x_i is not fixed; instead we have a range [A_i, B_i] and we need to compute sum_{x_1=A_1}^{B_1} ... sum_{x_N=A_N}^{B_N} f(x_1,...,x_N), modulo 1e9+7, where f is defined as:
For each distribution of C indistinguishable candies to N children (i.e., nonnegative integers a_1,...,a_N with sum a_i = C), we compute product over i of (x_i^{a_i}) = ∏ x_i^{a_i} = ∏ x_i^{a_i}? Actually happiness = x_i^{a} (the child gets a candies), and activity = product over i of happiness = ∏ x_i^{a_i}. Then f(x_1,...,x_N) = sum over all distributions of (∏ x_i^{a_i}) for all compositions a_i >=0 sum to C. So f(x) = ∑{a_1+...+a_N=C} ∏{i=1}^N x_i^{a_i}.
This is a known sum: it's the complete homogeneous symmetric polynomial of degree C in the N variables x_i: h_C(x_1,...,x_N) = ∑{a_i >=0, sum a_i = C} ∏ x_i^{a_i}. Alternatively, it's the coefficient of t^C in ∏{i=1}^N (1 - x_i t)^{-1}.
Thus f(x) = h_C(x_1,...,x_N). So we need to compute S = ∑{x_1=A_1}^{B_1} ... ∑{x_N=A_N}^{B_N} h_C(x_1,...,x_N) mod MOD.
Constraints: N, C up to 400, each A_i, B_i up to 400. So total ranges are small. But naive summing over all x_i combinations would be huge (range lengths up to 400 per coordinate, product up to 400^400 impossible). Need to use DP or combinatorial formulas.
Observation: h_C(x_1,...,x_N) is a symmetric polynomial? Not symmetric across children because we sum over all children but the x_i are independent variables. However, f is symmetric in the sense that if we permute indices, the sum would be symmetric, but here each child has its own range, not necessarily same. So we need to compute sum over each variable individually.
We need to compute S = ∑{x_1=A_1}^{B_1} ... ∑{x_N=A_N}^{B_N} ∑{a_1+...+a_N=C} ∏{i=1}^N x_i^{a_i}. Interchange sums: S = ∑{a_1+...+a_N=C} ∏{i=1}^N (∑{x_i=A_i}^{B_i} x_i^{a_i}). So define for each child i, and for each power d (0 <= d <= C), the sum of d-th powers over its range: S_i(d) = ∑{x=A_i}^{B_i} x^d. Then S = ∑{a_1+...+a_N=C} ∏{i=1}^N S_i(a_i). So essentially we have N sequences (over d) and we need the sum over compositions of C of the product of the S_i at those degrees.
This is reminiscent of convolution. If we define polynomials P_i(t) = ∑{d=0}^{C} S_i(d) t^d (or up to C), then the product over i of P_i(t) has coefficient for t^C equal to ∑{a_i sum C} ∏ S_i(a_i). So S = [t^C] ∏{i=1}^N P_i(t). Since N up to 400, C up to 400, we can multiply polynomials of degree up to C, each of size (C+1), N times. That's feasible: do DP: dp[k] = coefficient of t^k after considering first i children. Initially dp[0]=1, others 0. For each child i, we have array S_i[d] for d=0..C. Then new_dp[k] = ∑{d=0}^{k} dp[k-d] * S_i(d). Complexity O(NC^2) = 400400400 = 64e6, which is borderline but likely okay in Python with optimization, maybe using Numpy? But typical Python O(64e6) can be high but might pass with pypy? 64 million operations (multiplications and additions) mod 1e9+7 might be okay if coded carefully. But NC^2 worst-case 400400400 = 64,000,000, which is okay. Actually each step is convolution of two arrays length C+1, naive O(C^2). So overall O(N*C^2) ~ 64 million mod mul/adds. In Python, 64 million might be okay in PyPy (~1 sec per 100 million? Probably okay). We can also use NTT? Not needed. So the main challenge is computing S_i(d) = ∑_{x=A_i}^{B_i} x^d for d up to C (<=400). Need to compute these sums efficiently for each child.
Given ranges A_i, B_i up to 400, and d up to 400. We have up to NC sums = at most 400400=160,000. Each sum could be computed by iterating over the range: length L_i = B_i - A_i + 1 <= 400. So worst-case total operations to compute all S_i(d) would be sum_i (L_i * C) = at most N * 400 * 400 = 64,000,000 as well. That's also feasible. But careful: For each child i, for each d, sum over x from A_i to B_i of x^d mod MOD. Since L_i <= 400, d <= 400, exponentiation of numbers up to 400 to power 400 can be precomputed. Actually we can precompute powers: For all x from 1 to 400, compute pow[x][d] = x^d mod MOD for d=0..400. Then for each child i, S_i(d) = ∑{x=A_i}^{B_i} pow[x][d] . That's even faster: precompute pow[401][C+1]. Then for each child, for each d, sum over x from A_i to B_i: O(L_i) per d. But we can also precompute prefix sums of each power: For each d, precompute prefix sum PS[d][x] = ∑{t=1}^{x} t^d mod MOD. Then S_i(d) = PS[d][B_i] - PS[d][A_i-1]. That would be O(1) per child per d. So we need to precompute powers up to max B=400 (max value) and d up to C (<=400). Then compute prefix sums for each d.
Since N and C both up to 400, we can simply precompute for all d=0..C, for all x=0..maxB (max B_i) maybe 400, the cumulative sum. That's (C+1)401 ≈ 400401 ≈ 160k entries, trivial. So we can do: pow_table[x][d] maybe better as list of list. But we can compute directly: For d from 0 to C: pref[0] = 0; for x from 1 to maxX=400: pref[d][x] = pref[d][x-1] + pow_mod(x, d, MOD). Then for each child i, for d from 0 to C: S_i[d] = pref[d][B_i] - pref[d][A_i-1] mod MOD.
Thus overall algorithm:
-
Read N, C.
-
Read A list, B list.
-
Let maxX = max(B_i) = up to 400.
-
Precompute for d=0..C: powers of x up to maxX. Actually we can compute prefix sums directly without storing all powers: For each d, we can compute pow_x^d iteratively: start with val = 1 for x=0? But 0^0? Actually x can be 0? A_i >=1, so x >=1. So we can compute for each x from 1 to maxX: precompute p[x][d]? Or compute for each d: current = 1? Better: we can precompute p[x][d] by using pow function, but that's O(maxXClog?) But we can compute dynamic: For each x, compute x^d for d=0..C by repeated multiplication: p[x][0] = 1; for d=1..C: p[x][d] = p[x][d-1] * x % MOD. This costs O(maxX * C) = 400400=160k, fine. Then we can compute pref[d] as an array of length maxX+1: For each d, pref[d][0]=0; for x=1..maxX: pref[d][x] = (pref[d][x-1] + p[x][d]) % MOD. So need to store pref as list of lists, size (C+1)(maxX+1) ≈ 401*401=~160k integers. Good.
-
Then for each child i, compute S_i array length C+1: S_i[d] = (pref[d][B_i] - pref[d][A_i-1]) % MOD.
-
Then DP: dp = [0](C+1); dp[0] = 1. for i from 1 to N: new_dp = [0](C+1) for k from 0 to C: for d from 0 to k: new_dp[k] = (new_dp[k] + dp[k-d] * S_i[d]) % MOD dp = new_dp
But careful: This naive loop O(NC^2) = 64M. For each i, for each k, inner loop d up to k. This is about N * (C(C+1)/2) ≈ 400 * 400401/2 ≈ 400 * 80,200 = 32,080,000? Actually C=400 => sum_{k=0}^{C} (k+1) = (C+1)(C+2)/2 ≈ 400401/2 = 80,200. Multiply by N=400 => 32,080,000 operations. That's about 32 million, which is even better. Wait each operation includes multiplication and addition modulo. That's fine.
However, note: In each step we also need to consider d from 0 to min(C, k). But yes.
But we can also use convolution via NTT but not needed.
-
After processing all children, answer = dp[C].
But careful: The DP corresponds to product of polynomials P_i(t) = ∑{d=0}^{C} S_i(d) t^d. However, note: For each child, the sum over distributions includes a_i >= 0, and indeed the sum S_i(d) includes d=0 term: S_i(0) = ∑{x=A_i}^{B_i} x^0 = number of x in range (since x^0 = 1). That's correct because if child gets 0 candies, its happiness is x_i^0 = 1, independent of x_i, but in the sum over x_i, the factor becomes sum_{x_i} 1 = number of choices. So S_i(0) = B_i - A_i + 1. That's fine.
Thus DP will produce correct sum.
Now we need to verify with examples.
Example 1: N=2, C=3; A=[1,1], B=[1,1]. So each child's x only 1. Then S_i(d) = ∑{x=1}^{1} 1^d = 1 for all d. So P_i(t) = ∑{d=0}^3 1*t^d = 1 + t + t^2 + t^3 (but degree up to C, but infinite? Actually we only need up to C). The product for two children: (1 + t + t^2 + t^3)^2, coefficient of t^3 =? Ways: (0,3),(1,2),(2,1),(3,0) => 4. So answer = 4. matches.
Example 2: N=1, C=2, A=1,B=3. So S_1(d) = sum_{x=1}^3 x^d for d=0,1,2. So f(x) = h_2(x) = x^2? Wait for one child, h_C(x) = x^C? Actually with N=1, the only distribution is a_1=C, so product = x^C. So f(x) = x^C. Then sum_{x=1}^{3} x^2 = 1+4+9=14. So answer =14. Good.
Example 3: N=2, C=3, A=[1,1], B=[2,2]. So each child has x in {1,2}. Need sum over x1=1,2 and x2=1,2 of h_3(x1,x2). Let's compute manually to test: h_3(x,y) = sum_{a=0}^3 x^a y^{3-a} = x^0 y^3 + x^1 y^2 + x^2 y^1 + x^3 y^0. So for each (x,y) compute. Summation: (1,1): 1+1+1+1=4 (1,2): 0? Actually compute: a=0:1^02^3=8; a=1:14=4; a=2:12=2; a=3:11=1 => total 15? Wait 8+4+2+1=15. (2,1): 2^01^3=1; 2^11^2=2; 2^21=4; 2^31=8 => 15. (2,2): 2^02^3=8; 2^12^2=8; 2^22=8; 2^31=8? Actually 2^3*2^0=8 => total 32? Let's compute: 8+8+8+8=32. Sum = 4+15+15+32 = 66. matches example.
Thus DP should yield 66.
Example 4 and 5: large numbers, trust.
So solution seems straightforward.
But there is a nuance: The polynomial P_i(t) includes terms up to degree C, but in the DP we are only convolving up to C; higher terms not needed. However, what about the possibility that a child's S_i(d) for d up to C is defined, but actual distributions might need d up to C. So it's fine.
Now we must compute S_i(d) for d from 0 to C. However, note that sum_{x=A}^{B} x^d for d up to 400 can be computed as described using prefix sums. Since maxX <= 400, precomputation is cheap.
Edge Cases:
- A_i can be up to 400, B_i up to 400, but A_i <= B_i. So range length at least 1.
- MOD = 1e9+7.
Thus the solution is DP with precomputed sums.
Time Complexity: O(maxXC + NC^2) = O(400400 + 400160000? Actually NC^2 = 400160000=64,000,000, but earlier we computed 32 million? Let's recalc: For each child i, we need to convolve dp of length C+1 with S_i of length C+1. The naive convolution: for each output degree k (0..C), sum over d=0..k of dp[k-d]S_i[d]. This is exactly half of full convolution. The number of multiply-adds = sum_{k=0}^{C} (k+1) = (C+1)(C+2)/2. For C=400, that's about 401402/2 = 401201 = 80601? Let's compute: 401201 = 401*200 + 401 = 80200+401=80601. Actually earlier I got 80,200. That's about 80k per child. For N=400 => 32 million. That's fine.
But we need also inner loop modulo operations; we can reduce mod after accumulation, but careful with overflow. Python ints are arbitrary precision, but we will mod each multiplication result and addition. 32M operations is fine.
Potential improvements: we can use faster convolution like NTT or using numpy, but not necessary.
Memory: dp arrays of size ~401, S_i arrays similar.
Now let's verify the DP correctly yields the sum over compositions. Since S = sum_{a sum C} ∏ S_i(a_i). Our DP exactly computes that. So answer is dp[C].
One more nuance: Is there any factor for the distribution being "indistinguishable candies"? In the definition, the candies are indistinguishable, so distributions are just counts per child, which is exactly compositions. So correct.
Thus solution.
But careful: The sum S = ∑{x1..xN} f(x1..xN). And we interchanged sums: ∑{a sum C} ∏ ∑_{x_i} x_i^{a_i}. That's valid because finite sums and product.
Now ensure mod handling: Since MOD = 1e9+7, we need to compute all operations mod MOD. For prefix sums, subtract and add MOD to ensure non-negative.
Precomputation details:
-
Determine maxB = max(B_i). Let's call MAXV = 400 (as per constraints, but we can compute actual maximum). Since B_i <= 400.
-
We need powers up to maxB and degree up to C. So we can allocate p = [[0](C+1) for _ in range(maxB+1)]? Actually need p[x][d] for x from 1..maxB. Could also compute prefix sums directly without storing full p: For each d, compute cumulative sum as we go x from 1..maxB, compute x^d for each x. However computing x^d for each x,d separately might be repeated. Better: compute p[x][d] by iterative multiplication: For each x, p[x][0]=1; then for d=1..C: p[x][d] = p[x][d-1]x % MOD. This uses O(maxBC) memory. But we can also compute prefix sums on the fly without storing p: For each d, iterate x=1..maxB, compute val = pow(x,d,MOD) each time using fast exponent? That would be O(maxBClogC) slower but still okay (400400~9=1.44M). But storing p is fine; 401401 ~ 160k integers, that's trivial.
Actually we need prefix sums per d: pref[d][x] for d=0..C, x=0..maxB. That's (C+1)*(maxB+1) ≈ 160k, trivial. So we can compute p on the fly and accumulate.
We'll do:
MAXVAL = max(B_i) pref = [[0]*(MAXVAL+1) for _ in range(C+1)] # pref[d][x] = sum_{t=1}^{x} t^d mod MOD
for d in range(C+1): acc = 0 for x in range(1, MAXVAL+1): # compute x^d. Could use pow(x,d,MOD) each time; but we can compute incrementally if we loop d first? Actually we can compute all d for each x: # Better: For each x, compute all powers up to C, then fill pref[d][x] = pref[d][x-1] + p[x][d]. # Let's precompute power[x][d] for each x,d. # Since MAXVAL <= 400, C <= 400, allocate power = [[0]*(C+1) for _ in range(MAXVAL+1)]
power = [[1]*(C+1) for _ in range(MAXVAL+1)] # but we'll fill.
But we can compute: for x in range(1, MAXVAL+1): power[x][0] = 1 for d in range(1, C+1): power[x][d] = power[x][d-1] * x % MOD
Then compute pref: for d in range(C+1): acc = 0 for x in range(1, MAXVAL+1): acc = (acc + power[x][d]) % MOD pref[d][x] = acc
Alternatively we can compute pref directly without storing power by using running exponent values. But storing power is fine: (401*401)=160,801 entries, each an int, memory trivial.
Then for each child i: S_i = [0]*(C+1) for d in range(C+1): S_i[d] = (pref[d][B_i] - pref[d][A_i-1]) % MOD if S_i[d] < 0: S_i[d] += MOD
Now DP as described.
Potential improvements: Because DP will be repeated N times, we can combine all children in one DP. That's what we plan.
Now check example 4: N=4, C=8, A=[3,1,4,1], B=[3,1,4,1]; all ranges are single values: x1=3, x2=1, x3=4, x4=1. So we need sum_{x1=3,x2=1,x3=4,x4=1} h_8(x1,x2,x3,x4) = h_8(3,1,4,1). So answer should be 421749. We can test mentally? Not needed.
Edge Cases: C=0? C can be 1? But constraints say C>=1? Actually C>=1? Problem statement: 1≦C≦400. So C≥1, but DP can handle C=0 though not needed. But we can handle anyway.
Now implement.
Potential pitfalls:
-
The DP includes S_i(0) which is sum_{x} x^0 = number of integers in [A_i, B_i]. That's correct.
-
The DP uses modulo operations. Ensure dp is initialized size C+1.
Now compute for each child: we need S_i array. That's O(N*C) memory if we store all? But we can compute on the fly for each child and update DP, then discard S_i. So we can compute S_i for current child, do convolution, then move to next. That reduces memory.
Thus algorithm steps:
-
Read N, C.
-
Read list A, B.
-
maxB = max(B).
-
Precompute prefix sums pref[d][x] for d=0..C, x=0..maxB, where pref[d][0]=0, and for x>=1, pref[d][x] = sum_{t=1}^{x} t^d mod MOD.
To compute efficiently, we can compute power table as described.
Implementation details:
power = [[1]*(C+1) for _ in range(maxB+1)] for x in range(1, maxB+1): power[x][0] = 1 for d in range(1, C+1): power[x][d] = power[x][d-1] * x % MOD
pref = [[0]*(maxB+1) for _ in range(C+1)] for d in range(C+1): acc = 0 for x in range(1, maxB+1): acc = (acc + power[x][d]) % MOD pref[d][x] = acc
Alternatively, we can avoid storing power by computing on the fly: for d in range(C+1): acc=0; for x in range(1, maxB+1): acc = (acc + pow(x,d,MOD)) % MOD; pref[d][x]=acc. That uses pow each time, but pow is fast. But I'll go with power table for simplicity.
-
DP: dp = [0]*(C+1); dp[0] = 1
For i in range(N): a = A[i]; b = B[i] S = [0](C+1) for d in range(C+1): val = pref[d][b] - (pref[d][a-1] if a>=1 else 0) S[d] = val % MOD # convolve dp and S new_dp = [0](C+1) for k in range(C+1): total = 0 # we could loop d from 0 to k # To reduce modulo operations, we can accumulate in Python int and then mod, but Python ints can become large but still fine. However we need mod after sum. # But we can do: for d in range(k+1): total = (total + dp[k-d] * S[d]) % MOD # Let's do typical: for d in range(k+1): total = (total + dp[k-d] * S[d]) % MOD new_dp[k] = total dp = new_dp
After loop, answer = dp[C] % MOD (should already be modded). Print.
Now complexity: O(maxBC) for precomp, O(NC^2) for DP.
Now test with given examples.
But note: In example 3, our precomp with maxB=2, C=3 works.
Now potential improvements: We can use faster convolution via NTT because C is small, not needed.
Edge Cases: If A_i=1, then pref[d][0] is 0, fine.
Now check mod handling: when subtracting pref[d][a-1], if a-1=0, pref[d][0] is 0, as we defined. We need to ensure pref[d] array is defined for index 0 as 0. In our pref generation, we started x from 1, so pref[d][0] is left as default 0. So ok.
Now compute for N=400, C=400, DP loop: about 400*80k = 32 million inner iterations. In Python, 32 million multiplications and additions mod 1e9+7 may be okay in PyPy (maybe 1-2 seconds). But we need to be careful about overhead in Python loops. Might be borderline but likely fine given constraints. We can optimize by using list comprehension or using some tricks.
We can reduce constant factor: For each child, we can compute new_dp as convolution via nested loops, but we can also do standard DP:
new_dp = [0]*(C+1) for d in range(C+1): if S[d] == 0: continue sd = S[d] for k in range(d, C+1): new_dp[k] = (new_dp[k] + dp[k-d] * sd) % MOD
That loops over d then k, and total operations same: sum_{d=0}^{C} (C-d+1) = (C+1)(C+2)/2 as well, but the inner loop avoids if-check on d each time and reduces indexing maybe. Actually the original loop for k from 0..C and inner d from 0..k is similar. The alternative loops d from 0..C and k from d..C, which also yields same count but may be more cache-friendly? Possibly. But either is fine.
We'll implement the d-outer loop, because it's easier: we iterate d, multiply dp by sd and add to new_dp shifted by d. That is essentially:
new_dp = [0]*(C+1) for d in range(C+1): sd = S[d] if sd == 0: continue for k in range(0, C+1-d): new_dp[k+d] = (new_dp[k+d] + dp[k] * sd) % MOD
But careful: The original dp is from previous children; we want to add contributions from the current child taking d candies. So we can do:
new_dp = [0]*(C+1) for d in range(C+1): if S[d]==0: continue for k in range(C+1-d): new_dp[k+d] = (new_dp[k+d] + dp[k] * S[d]) % MOD
Yes that's typical.
Now complexity: same.
We can also precompute S_i for each child, but we can compute on the fly.
Now overall plan: implement.
But there is a nuance: The DP product of polynomials is indeed the sum over compositions, but we must ensure that the sum S_i(d) is computed correctly modulo MOD.
Now test with sample 1:
N=2, C=3; A=[1,1] B=[1,1]; maxB=1; precomp: for x=1, powers: 1^d =1 for all d. pref[d][1]=1. For each child: S[0]=1 (since range length 1, x^0=1), S[1]=1, S[2]=1, S[3]=1. DP:
Initialize dp[0]=1. First child: S=[1,1,1,1]. Then new_dp: d=0: sd=1, for k=0..3: new_dp[0+0] += dp[0]*1 => new_dp[0]=1 d=1: for k=0..2: new_dp[0+1] += dp[0]*1 => new_dp[1]=1 d=2: new_dp[2] += dp[0] => new_dp[2]=1 d=3: new_dp[3] += dp[0] => new_dp[3]=1 => dp becomes [1,1,1,1]. Second child: same S. new_dp reset. Then: d=0: new_dp[0] += dp[0]*1 =1 d=1: for k=0..2: new_dp[1]+=dp[0]*1 => +1; new_dp[2]+=dp[1]*1? Wait: careful: loop over k from 0 to C-d: for d=1, k=0..2: new_dp[k+1] += dp[k]*1. So new_dp[1] += dp[0]=1; new_dp[2] += dp[1]=1; new_dp[3] += dp[2]=1. So after d=1: new_dp[1]=1, new_dp[2]=1, new_dp[3]=1. d=2: for k=0..1: new_dp[2] += dp[0]=1 => becomes 2; new_dp[3] += dp[1]=1 => becomes 2. d=3: for k=0..0: new_dp[3] += dp[0]=1 => becomes 3? Actually new_dp[3] currently from d=1:1, d=2: +1 =>2, d=3: +1 =>3. But expected final dp[3] = coefficient = 4. Hmm, we got 3? Let's compute carefully.
But note that we should also include d=0? Already included. After d=0: new_dp[0] = dp[0] *1 =1. Then d=1: add dp[0] to new_dp[1]; dp[1] to new_dp[2]; dp[2] to new_dp[3]; d=2: add dp[0] to new_dp[2]; dp[1] to new_dp[3]; d=3: add dp[0] to new_dp[3]; Also what about dp[3]? For d=0, we also added dp[1], dp[2], dp[3]? Wait for d=0: the loop for k from 0 to C-d = C: so k=0..3: new_dp[k+0] += dp[k]*S[0]. S[0] =1. So new_dp[0] gets dp[0]; new_dp[1] gets dp[1]; new_dp[2] gets dp[2]; new_dp[3] gets dp[3]. dp[3] initially is 1 after first child? Actually after first child, dp = [1,1,1,1]. So in d=0 step, new_dp[0] gets dp[0]=1; new_dp[1] gets dp[1]=1; new_dp[2] gets dp[2]=1; new_dp[3] gets dp[3]=1. So after d=0, new_dp = [1,1,1,1]. Then d=1: new_dp[1] += dp[0]=1 => becomes 2; new_dp[2] += dp[1]=1 => becomes 2; new_dp[3] += dp[2]=1 => becomes 2. Then d=2: new_dp[2] += dp[0]=1 => becomes 3; new_dp[3] += dp[1]=1 => becomes 3. Then d=3: new_dp[3] += dp[0]=1 => becomes 4. So final dp[3]=4. Yes correct. So algorithm works.
Now for sample 3:
N=2, C=3, A=[1,1], B=[2,2]; maxB=2. Precompute powers and pref. For each child, S(d) = sum_{x=1}^{2} x^d = 1^d+2^d. So S(0)=2, S(1)=1+2=3, S(2)=1+4=5, S(3)=1+8=9.
First child: dp after first child should become S itself? Actually DP: start dp0=[1,0,0,0]. After first child: new_dp = S (since only one child, coefficient for degree k is S(k)). So dp = [2,3,5,9]? But careful: For single child, the sum over compositions of a single variable is just S_i(d) where d = C? Actually with one child, the sum over distributions with total C is just that child gets exactly C candies, so the contribution is S_i(C). But DP after first child should produce the polynomial P_1(t) = ∑ S_1(d) t^d. Yes so dp becomes exactly S array. So after first child: dp = [2,3,5,9].
Second child: convolve with S again. Compute coefficient of t^3. That is sum_{d=0}^3 dp[d] * S[3-d] = dp[0]S[3] + dp[1]S[2] + dp[2]S[1] + dp[3]S[0] = 29 + 35 + 53 + 92 = 18+15+15+18=66. Correct.
Thus DP correct.
Now consider sample 5: N=3, C=100, A=[7,6,5], B=[9,9,9]; maxB=9, C=100. However C is 100 but note that B_i <=9, and C is up to 400. But we precompute powers for x up to 9, degree up to 100. That's fine. The DP will be N=3, C=100, so about 3 * (101102/2) ≈ 35151=15453 operations, trivial. But we also need to compute S_i(d) for d up to 100, which is fine. So the solution will handle C up to 400 even if maxB is small.
But wait: The DP O(NC^2) is O(400160000)=64M if C=400 and N=400. That's the worst-case. As we computed earlier, it's about 32M operations? Actually careful: The convolution loops: for each child, for d from 0 to C, for k from 0 to C-d: total iterations = (C+1)(C+2)/2. For C=400, that's about 401402/2 = 401201 = 80601. Multiply by N=400 => 32,240,400. So about 32 million. That's fine.
But there's also the inner multiplication and addition mod. So overall should be okay.
Now ensure to use PyPy for speed. Also we can micro-optimize: Use local variables for MOD, dp, S, etc. Use list comprehension or manual loops.
We need to precompute prefix sums up to maxB, which is max(B_i). That maxB could be as large as 400. So power table size 401x401 (since C up to 400). Pref same size. Memory fine.
Now consider also we could compute S_i(d) for all children before DP? But we can compute on the fly to save memory.
Potential improvement: Since the S_i arrays may be same for children with identical [A_i,B_i] intervals. But not necessary.
Now edge case: N up to 400, but maybe some A_i > B_i? No, given A_i <= B_i.
Now check modulo: 10^9+7.
Implementation details: Use sys.stdin.read to read all ints quickly.
Let's outline code:
import sys MOD = 10**9+7
def main(): data = list(map(int, sys.stdin.read().split())) it = iter(data) N = next(it); C = next(it) A = [next(it) for _ in range(N)] B = [next(it) for _ in range(N)] maxB = max(B)
# precompute powers and prefix sums # create pref as list of lists: pref[d][x] for d=0..C, x=0..maxB # Actually we need pref[d][x] for x up to maxB. We'll allocate (C+1) lists each length (maxB+1). pref = [[0]*(maxB+1) for _ in range(C+1)] # compute power for each x and d, accumulate # We'll compute for each d separately using pow? But we can compute using iterative multiplication. # Let's compute power matrix: power[x][d] for x in 0..maxB? Actually x from 1..maxB. We'll store power for each x and d. # Since maxB and C are small, compute directly: # But we can compute pref without storing power: for d in range(C+1): # acc = 0 # for x in range(1, maxB+1): # acc = (acc + pow(x, d, MOD)) % MOD # pref[d][x] = acc # That's simple and uses only O(C*maxB) time, and pow built-in is fast. # However, pow(x,d,MOD) for each (x,d) pair 400*400=160k times, each pow is O(log d) maybe but with small exponent 400 it's fast (maybe using exponentiation by squaring but Python's built-in pow uses exponentiation by squaring, still fine). Could precompute to avoid repeated pow but it's fine. # But we can also compute with iterative multiplication per x: for each x compute x^0..x^C sequentially. # Let's do the iterative method to be efficient. # We'll compute power list of lists: power = [[1]*(C+1) for _ in range(maxB+1)]; but we only need pref, not power afterwards. # Approach: for x in range(1, maxB+1): # pow_x = [1]*(C+1) # for d in range(1, C+1): # pow_x[d] = pow_x[d-1] * x % MOD # # now add to pref columns # for d in range(C+1): # pref[d][x] = (pref[d][x-1] + pow_x[d]) % MOD # But note: we need pref[d][x] defined for each d. We can accumulate as we go. # Initialize pref[d][0] = 0 for all d. # Then iterate x=1..maxB: # compute pow_x for all d. # for d in range(C+1): # pref[d][x] = (pref[d][x-1] + pow_x[d]) % MOD # This uses O(maxB*C) time and O(C*maxB) memory for pref, plus O(C) temporary per x. # That's fine. # Implementation: for d in range(C+1): pref[d][0] = 0 for x in range(1, maxB+1): pow_x = [1]*(C+1) for d in range(1, C+1): pow_x[d] = pow_x[d-1] * x % MOD for d in range(C+1): pref[d][x] = (pref[d][x-1] + pow_x[d]) % MOD # Now DP dp = [0]*(C+1) dp[0] = 1 for i in range(N): a = A[i] b = B[i] # Compute S_i for d=0..C S = [0]*(C+1) # Use pref to get sum from a to b inclusive for d in range(C+1): val = pref[d][b] - pref[d][a-1] # a>=1 S[d] = val % MOD # Convolve dp and S new_dp = [0]*(C+1) # For each d with S[d]!=0, update for d in range(C+1): sd = S[d] if sd == 0: continue # For k from 0 to C-d: # new_dp[k+d] += dp[k] * sd # We'll use local variables for speed dp_k = dp ndp = new_dp # typical loop limit = C - d for k in range(limit+1): ndp[k+d] = (ndp[k+d] + dp_k[k] * sd) % MOD dp = new_dp print(dp[C] % MOD)if name == "main": main()
Now check with sample inputs.
But we need to be careful: In the loops for constructing pref, we had nested loops: for x in 1..maxB, compute pow_x for all d, then for d in 0..C update pref[d][x]. That's fine. But we need to initialize pref[d][0] = 0. Already done.
Now test quickly mentally:
Sample 1: N=2, C=3, maxB=1. pref[d][1] = sum_{x=1}^1 x^d = 1. Then for each child a=1,b=1: S[d] = pref[d][1] - pref[d][0] = 1. DP yields 4.
Sample 2: N=1, C=2, maxB=3. pref[0][1]=1, pref[0][2]=2, pref[0][3]=3; pref[1][1]=1, [2]=1+2=3, [3]=3+3=6; pref[2][1]=1, [2]=1+4=5, [3]=5+9=14. Child a=1,b=3 => S[0]=3, S[1]=6, S[2]=14. DP start dp[0]=1; after child: new_dp = convolution of [1,0,0] with S => basically S itself? Actually with one child, new_dp[k] = S[k] for k up to C? Let's compute: for d=0: new_dp[0] += dp[0]S[0] = 13=3. For d=1: new_dp[1] += dp[0]*S[1] = 6; for d=2: new_dp[2] += dp[0]*S[2] = 14. So dp = [3,6,14]. answer = dp[2] = 14. Correct.
Sample 3: N=2, C=3, maxB=2. pref computed: For x=1,2. pref[d][0]=0. pref[0][1]=1, [2]=2; pref[1][1]=1, [2]=1+2=3; pref[2][1]=1, [2]=1+4=5; pref[3][1]=1, [2]=1+8=9. For each child a=1,b=2: S[d] = pref[d][2] - pref[d][0] = pref[d][2]. So S = [2,3,5,9]. DP yields 66.
Looks good.
Now sample 4: N=4, C=8, A=[3,1,4,1], B same. maxB=4. Pref compute. DP should produce 421749. We trust.
Sample 5: as given.
Thus solution is correct.
But we need to be mindful of modulo when subtracting: val = pref[d][b] - pref[d][a-1]; then val % MOD. Since we mod after each addition, pref values are in [0, MOD-1], and a-1 >=0; but we must ensure a-1 is valid index. If a=1, a-1=0, pref[d][0] is defined as 0. So ok.
One more potential: The DP uses new_dp = [0]*(C+1) each iteration. That's fine.
Now time: precomp: maxB up to 400, C up to 400 => for each x (400), we compute pow_x list of length C+1 (401) by repeated multiplication (C operations) => 400400 = 160k multiplications. Then for each d (401) we update pref[d][x] with addition, that's also 400400 = 160k additions. So precomp total ~320k ops, negligible.
DP: ~32M iterations, each doing multiplication, addition, modulo. In Python, 32M may be around 0.5-1 sec in PyPy if optimized. We'll try to reduce modulo operations: Instead of doing % MOD inside inner loop for each addition, we could accumulate using integer and then mod after each k? But the product dp[k] * sd could be up to MOD^2 ~ 1e18, Python int can handle, but adding many such may become large; but the number of adds per new_dp entry can be up to C+1 = 401, and MOD^2 ~ 1e18, sum of up to 401 such terms ~ 4e20, still within Python's arbitrary precision, but could be slower due to big ints. Better to mod each addition to keep numbers small. However, we can do: new_dp[k+d] = (new_dp[k+d] + dp[k] * sd) % MOD. That's fine. We could also use if statements to reduce mod operations: compute tmp = dp[k] * sd; new_dp[k+d] += tmp; if new_dp[k+d] >= MOD2: new_dp[k+d] -= MOD2? But not straightforward because addition could exceed MOD many times. We can use modulo after each addition for simplicity.
We can also use list comprehension with convolution via Python's built-in? Not needed.
But note: Since we have many children, we can try to combine identical children? Not necessary.
One more optimization: If S[d] is zero for many d, we can skip. For a given child, S[d] = sum_{x=A}^{B} x^d. For d>0, this sum is positive, but mod may be zero? Unlikely but possible? Could be multiple of MOD? Since MOD is large (1e9+7) and numbers are up to 400^400 huge, but we compute modulo. The sum could be 0 mod MOD if the sum is exactly multiple of MOD, but that's possible but rare. So skipping zero may save a few iterations but not significant.
But for d=0, S[0] = (B-A+1). That's not zero (since A <= B). So S[0] > 0 mod MOD, though could be multiple of MOD? Length up to 400, so not zero.
Thus all S[d] are positive mod MOD (unless MOD divides the sum). So skipping zero may not skip much.
Nevertheless, we can still keep the continue.
Now ensure we correctly handle when a-1 > maxB? a >=1, so a-1 >=0 <= maxB. pref defined for indices 0..maxB. Good.
Now we should test with large cases to ensure performance. Could also implement DP with alternative loop order: for k in range(C+1): new_dp[k] = sum_{d=0}^k dp[k-d]*S[d]. This might be slightly slower because for each k we have inner loop d. The d-outer loop may be more cache-friendly because we are updating new_dp in increasing order with fixed d. Usually the d-outer loop is faster because we multiply dp[k] by constant sd and add to new_dp[k+d], and we can use Python's built-in range. But both are similar. We'll stick with d-outer.
One more micro-optimization: Use local variables for dp, new_dp, C, MOD, and maybe use append? Not needed.
We'll write:
for i in range(N): a = A[i]; b = B[i] S = [0](C+1) for d in range(C+1): S[d] = (pref[d][b] - pref[d][a-1]) % MOD new_dp = [0](C+1) for d, sd in enumerate(S): if sd: # loop k from 0 to C-d nd = new_dp dpk = dp for k in range(C-d+1): nd[k+d] = (nd[k+d] + dpk[k] * sd) % MOD dp = new_dp
But careful: In the inner loop, we are modifying new_dp while reading dp, that's fine.
Now consider if we have many children and C=400, DP per child 80k iterations; 400 children => 32 million. Each iteration does multiplication, addition, modulo. This should be okay.
But we can also note that the DP is basically computing product of polynomials; we could use exponentiation by squaring? Not needed.
One more nuance: The polynomial P_i(t) is of degree up to C, but the sum S_i(d) for d up to C can be precomputed. However, note that the actual maximum degree needed for each child is C because a child cannot receive more than C candies. So that's fine.
Now confirm constraints: A_i, B_i up to 400. So the prefix sums computed up to 400.
Now edge: If B_i is less than A_i? Not possible.
Now let's think about if there is any alternative combinatorial formula: possibly using generating functions and polynomial multiplication. Already using DP.
Now confirm with sample 4: We can compute manually? Not needed.
Now we should test with small random case to ensure correctness. But since it's reasoning, I'll trust.
Now let's think about potential pitfalls: The DP sums over all compositions of C, but S_i(d) includes d=0 term. However, for a child, if it gets 0 candies, the factor contributed from the sum over x_i is S_i(0) = number of possible x_i values, which is correct because the happiness factor is 1 regardless of x_i, and the activity product includes factor 1, and sum over x_i of 1 is the count. So all good.
Now what about the possibility that we might double count? No.
Now time to write final solution.
But before finalizing, we need to be careful about memory: pref is a list of (C+1) lists each of length maxB+1. With C=400, maxB=400, that's 401*401 ~ 160k integers, fine.
But note: we also compute pow_x for each x, which is a list of length C+1, but we create a new list each iteration. That's 400 * 401 integers temporary, also fine.
Alternative: we can compute pref without temporary pow_x, by using cumulative updates: For each d, we can compute pow(x,d) on the fly using pow function, but that might be slower due to repeated pow calls? But not too bad. However, the current method is fine.
But we could also compute pref by building a table pow_table[x][d] first, then compute prefix sums. Let's do:
pow_table = [[0]*(C+1) for _ in range(maxB+1)] for x in range(1, maxB+1): pow_table[x][0] = 1 for d in range(1, C+1): pow_table[x][d] = pow_table[x][d-1] * x % MOD
pref = [[0]*(maxB+1) for _ in range(C+1)] for d in range(C+1): acc = 0 for x in range(1, maxB+1): acc = (acc + pow_table[x][d]) % MOD pref[d][x] = acc
That uses more memory (pow_table: 401*401 ints) but still fine.
But we can avoid storing pow_table by computing on the fly as earlier. I'll choose the on-the-fly method to avoid storing an extra 2D list (but it's not huge). Actually both are okay.
Now let's think about time for DP. 32M iterations, each doing:
new_dp[k+d] = (new_dp[k+d] + dp[k] * sd) % MOD
That's a multiplication and addition and modulo. In Python, modulo is relatively expensive. We can reduce number of modulo operations by using if statements to subtract MOD when the sum exceeds some threshold. Since dp[k] and sd are both less than MOD, their product is less than MOD^2 ≈ 1e18. Adding to new_dp[k+d] which may also be up to MOD-1. So new_dp[k+d] could become up to about MOD^2 + MOD. To keep numbers bounded, we could use:
tmp = new_dp[k+d] + dp[k] * sd if tmp >= MOD: tmp %= MOD new_dp[k+d] = tmp
But modulo operation on Python is relatively fast; still 32M modulo operations may be okay.
Alternatively, we could use:
new_dp[k+d] += dp[k] * sd if new_dp[k+d] >= MOD: new_dp[k+d] %= MOD
But that might still require modulo after each addition. Or we could accumulate in a local variable and mod at the end of each d loop? For each d, we update new_dp entries. The same entry new_dp[k+d] may be updated multiple times for different d. So we cannot delay mod beyond one full d loop, because after many updates the value could become huge (up to N*MOD^2 maybe). But within a single d loop, each new_dp entry is updated only once? Actually for fixed d, each new_dp[k+d] gets contributions from only one k (since k loops over all possible, each output index is unique for a given d? Wait: For a fixed d, as k varies from 0 to C-d, each index (k+d) is distinct because k is increasing. So each new_dp position gets at most one addition from a given d. But across different d values, the same new_dp index may be updated multiple times. So within a single d loop, we could avoid modulo after each addition, but after finishing the d loop we could mod the entire new_dp array. However, the product dp[k]*sd could be up to MOD^2 ~ 1e18, and we sum at most (C+1) such terms across d loops, but within a d loop, the addition is only one term per index, so the value after d loop (before
-