Descripción

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

Especificación de entrada

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.

Especificación de salida

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)~.

Ejemplo de entrada

8 15
53101831
523435110182319

Ejemplo de salida

4