Gene Mutation¶
- Indicative time limit: 0.5 seconds (reference environment: environment and measurements)
- Actual time limit: twice the reference program's baseline time on the slowest official test file in the target environment, rounded up to a multiple of 0.5 seconds; round up further if the platform requires a coarser unit.
- Memory limit: 128 MB
Story¶
After testing the cloning vats, Yuri's laboratory begins studying gene mutations. A gene is a sequence of digits. Mutation preserves the digits but changes each position's contribution to its ability. Given a standard gene and a numerical upper bound, count the genes whose mutated ability exceeds the standard.
Formal Problem Statement¶
You are given two base parameters \(n,m\) . Write a nonnegative integer \(x\) in base \(n\) , then replace each positional weight, a power of \(n\) , with the corresponding power of \(m\) . If its digits from least to most significant are \(x_0,\ldots,x_{L-1}\) , its mutated ability is
Each digit satisfies \(0\le x_i<n\) . A digit may be at least \(m\) : evaluate the formula directly, without requiring valid base-\(m\) digits.
The standard gene \(A\) and upper bound \(B\) are both given in base \(n\) . Count the integers \(x\) satisfying \(0\le x\le B\) and \(F(x)>F(A)\) , modulo \(10^9+7\) . The upper-bound comparison uses ordinary base-\(n\) values; the ability comparison uses \(F\) .
Input Format¶
The first line contains \(n,m,L_A,L_B\) . The second line contains the \(L_A\) digits of \(A\) , most significant first. The third contains the \(L_B\) digits of \(B\) in the same order.
Output Format¶
Print the required count modulo \(10^9+7\) .
Sample 1¶
Input¶
10 2 1 3
0
1 0 0
Output¶
100
Explanation¶
The standard ability is zero. Every integer from \(1\) through \(100\) has positive ability.
Sample 2¶
Input¶
10 2 1 2
1
1 0
Output¶
9
Explanation¶
Among integers from \(0\) through \(10\) , only \(0,1\) have ability at most \(F(A)=1\) , leaving \(9\) valid integers.
Sample 3¶
Input¶
10 2 1 3
5
1 0 0
Output¶
88
Explanation¶
For integers from \(0\) through \(99\) , decimal digits \(a,b\) give ability \(2a+b\) . Exactly \(6+4+2=12\) have ability at most \(5\) . The ability of \(100\) is \(4\) , so it also fails. The answer is \(101-13=88\) .
Sample 4¶
Input¶
2 3 2 2
1 0
1 1
Output¶
1
Explanation¶
The candidates are binary \(0,1,10,11\) , with abilities \(0,1,3,4\) . Only \(11\) strictly exceeds the standard ability of \(10\) .
Constraints and Guarantees¶
- \(2\le n,m\le30\) and \(1\le L_A,L_B\le20000\) .
- Every digit is between \(0\) and \(n-1\) .
- Neither number has leading zeros; zero is represented by one digit \(0\) .
Test Groups¶
| Score share | Additional conditions |
|---|---|
| 100% | No additional conditions |