3330 - Hades and the Number of the Witch

Created by Luis Manuel Díaz Barón
Added by luismo (2015-06-14)
Limits
Total Time: 15000 MS | Test Time: 1500 MS |Memory: 256 MB | Output: 64 MB | Size: 16 KB
Enabled languages
Available in

Description

The witch lives in a house deep in the forest, where no one can find her. The only way to ask for her services is calling her by phone. Her phone number is represented as a string P which contains only digits and she always encrypts it into a similar string S.

Hades is their assistant and the only one who knows her phone number. He gives you the value of S and you want to count the number of ways the phone number P can be found as a sub-sequence of S. Remember that a sub-sequence of any string is a sequence of their characters (in increasing order of their indices and not necessarily consecutive). Also a sub-sequence of a string could be the string itself.

For example: if the number P is 53101831 and S is 52343511018231, P can be found four times as a sub-sequence of S:
523435110182319
523435110182319
523435110182319
523435110182319
La bruja vive en una casa de lo profundo del bosque, donde nadie puede encontrarla. La única manera de pedir sus servicios es llamando por teléfono. Su número de teléfono se representa como una cadena P que contiene sólo dígitos y ella siempre la encripta en una cadena similar S.

Hades es su asistente y el único que conoce su número de teléfono. Él le da el valor de S y usted desea contar el número de formas en que el número de teléfono de P se puede encontrar como un sub-secuencia de S. Recuerde que una sub-secuencia de cualquier cadena es una secuencia de sus caracteres (en orden creciente de sus índices y no necesariamente consecutivos). También una sub-secuencia de una cadena podría ser la propia cadena.

Por ejemplo: si el número P es 53101831 y S es 52343511018231, P se puede encontrar en cuatro ocasiones como una sub-secuencia de S:
523435110182319
523435110182319
523435110182319
523435110182319
The witch lives in a house deep in the forest, where no one can find her. The only way to ask for her services is calling her by phone. Her phone number is represented as a string P which contains only digits and she always encrypts it into a similar string S.

Hades is their assistant and the only one who knows her phone number. He gives you the value of S and you want to count the number of ways the phone number P can be found as a sub-sequence of S. Remember that a sub-sequence of any string is a sequence of their characters (in increasing order of their indices and not necessarily consecutive). Also a sub-sequence of a string could be the string itself.

For example: if the number P is 53101831 and S is 52343511018231, P can be found four times as a sub-sequence of S:
523435110182319
523435110182319
523435110182319
523435110182319

Input specification

The first line contains two integer numbers M (8 <= M <= 10) and N (1 <= N <= 10^5) representing the length of the phone number of the witch P and the length of the string S respectively. The second line contains a string P of exactly M digits between 0 and 9, denoting the phone number of the witch. The third and last line of input contains the string S, containing exactly N digits between 0 and 9.
La primera línea contiene dos números enteros M (8 <= M <= 10) y N (1 <= N <= 10^5) que representan la longitud del número de teléfono P de la bruja y la longitud de la cadena S, respectivamente. La segunda línea contiene una cadena P de exactamente M dígitos entre 0 y 9, que indica el número de teléfono de la bruja. La tercera y última línea de entrada contiene la cadena S, que contiene exactamente N dígitos entre 0 y 9.
The first line contains two integer numbers M (8 <= M <= 10) and N (1 <= N <= 10^5) representing the length of the phone number of the witch P and the length of the string S respectively. The second line contains a string P of exactly M digits between 0 and 9, denoting the phone number of the witch. The third and last line of input contains the string S, containing exactly N digits between 0 and 9.

Output specification

Output a line with an integer representing the number of ways the phone number P can be found as a sub-sequence of S. As this number may be large, output the remainder of dividing the number by 1000000007 (10^9 + 7).
Usted debe imprimir una línea con un entero que representa el número de formas en que el número de teléfono de P se puede encontrar como un sub-secuencia de S. Como este número puede ser grande, imprima el resto de la división del número por 1000000007 (10^9 + 7).
The first line contains two integer numbers M (8 <= M <= 10) and N (1 <= N <= 10^5) representing the length of the phone number of the witch P and the length of the string S respectively. The second line contains a string P of exactly M digits between 0 and 9, denoting the phone number of the witch. The third and last line of input contains the string S, containing exactly N digits between 0 and 9.

Sample input

8 15
53101831
523435110182319

Sample output

4

Hint(s)