String Sets
Practice
3.7 (3 votes)
Combinatorics
Hard
Inclusion Exclusion
Math
Generating functions
Problem
82% Success 1166 Attempts 50 Points 3s Time Limit 256MB Memory 1024 KB Max Code

Let's define the weight of an English letter (lowercase or uppercase) in the following way: a has weight 1, b = 2, and so on until z = 26; A = 27 and so on until Z = 52. The weight of an alphabetic string is the sum of weights of all letters it contains, modulo M.

Next, let's define the sum of two strings X and Y of length N consisting of lowercase English letters as a string Z of length N such that for each valid i, the weight of the i-th character of Z is the sum of weights of the i-th characters of X and Y. For example, the sum of strings "abzaa" and "abcde" is the string "bdCef".

enter image description here

You are given a string S of lowercase English letters with length N and two integers M and K. You need to select a string B (also consisting only of lowercase English letters) such that the sum of strings S and B has weight K.

Can you find the number of ways to select the string B modulo \( 10^9+7 \)?

Constraints

  • \( 1 \le N \le 200,000 \)

  • \( 100,000 \le M \le 1,000,000,007 \)

  • \( 0 \le K < M \)

  • the string S will consist only of lowercase English letters

Input format

The first line of the input contains three space-separated integers N, M and K.

The second line contains a single string S of length N.

Output format

Print a single line containing one integer — the answer modulo \( 10^9+7 \).

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:50
5 votes
Tags:
CombinatoricsInclusion-exclusionC++Math
Points:50
Tags:
Centroid decompositionDisjoint setHardInclusion ExclusionInclusion exclusion principleMathTrees
Points:50
6 votes
Tags:
ApprovedDynamic ProgrammingFast Fourier transformHardMathOpen