Shash and Exun Celebrations
All submissions for this problem are available.
Shash is the richest man in the world by a long shot. Exun 2042, DPS RK Puram’s 42nd (assume it was cancelled deliberately for 5 years to sync up ;) ) Tech Festival is coming and Shash is delighted. He decides to pay his employees extra to celebrate the occasion. So he decides to draw a cheque with a value V that is to be distributed amongst his employees.
- V must be an integral value between A and B (inclusive). The number of digits in A and B is equal.
- Suppose Shash assigns 1 based indexing to the digits of this number V. He doesn’t like digits at indexes divisible by K. Neither does he like the digit L. So he puts L only at indexes divisible by K, and nowhere else.
- Shash Evil Incorporative has M employees and 1 teaboy. He must give an equal integral amount to all the M employees and the teaboy must be paid a fixed value X. X will always be less than M. The whole value V should be used up in making this payment.
Find the number of V’s (mod 1e9+7) that Shash can choose such that these constraints are satisfied.
The first line contains 4 integers, K, L, M and X as described above.
The second line contains the lower limit on V in the form of a string A.
The third line contains the upper limit on V in the form of a string B.
A single integer, the number of possible values mod 1e9+7
- 1 <= |A| = |B| <= 1,000
- X < M <= 1,000
|A|, |B| <= 8
Subtask 2 (20 Points):
M = 2, 5 or 10
Subtask 3 (70 Points)
Example: Sample Input 1: 2 5 6 2 100 199 Sample Output 1: 2 Explanation 1: Only 2 numbers, 152 and 158 satisfy the constraints. For 152, 30 are given to each employee. For 158, 31 are given to each employee. Both have the digit 5 only in places divisible by 2. Sample Input 2: 3 5 5 0 100 200 Sample Output 2: 9 Explanation 2: 105, 115, 125, 135, 145, 165, 175, 185, 195 are the possible values. Notice that 155 also has 5 in the 2nd place and 2 is not divisible by 3, so it is not counted. Sample Input 3: 2 5 2 1 1 9 Sample Output 3: 4 Explanation 3: 1 3 7 9 are the possible values. Again notice that 5 cannot be a possible value as it can only be in positions divisible by 2.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS|
Fetching successful submissions