Rhezo and Division
Practice
5 (5 votes)
Algorithms
Dynamic programming
Medium
Ready
Z algorithm
Z Algorithm
Problem
74% Success 370 Attempts 30 Points 1s Time Limit 256MB Memory 1024 KB Max Code

Rhezo calls a number good if the number is divisible by all numbers from 1 to 9. His father also likes good numbers, and has promised him to buy 1 chocolate per every good number he tells him. He doesn't want to make the task simple for Rhezo, therefore he gives him 2 strings T and P.

He tells Rhezo to find the number of ways to select one or more occurrences of P in T, so that the product of starting positions of all those occurrences is a good number. Rhezo likes chocolates and is not so good at programming. Help him. As the answer could be large, output the answer modulo \(10^9+7\).

Input:

First line contains the string P. Second line contains the string T.

Output:

Help Rhezo to find the number of ways to select one or more occurrences of P in T, so that the product of starting positions of all those occurrences is a good number.

Constraints:

Length of \(S, T \le 10^4\)

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:30
7 votes
Tags:
AlgorithmsKMP AlgorithmMediumOpenString ManipulationZ algorithmZ-algorithm
Points:30
13 votes
Tags:
ApprovedHash MapsMediumReadyString ManipulationZ algorithmZ-algorithm
Points:30
17 votes
Tags:
AlgorithmsApprovedKMP AlgorithmMediumZ algorithmZ-algorithm