Dada una matriz de ~n \times m~ donde cada casilla tiene un color. En base a ella se forma una matriz de ~na \times mb~ colocando copias de la matriz original ~a~ veces abajo y ~b~ veces una al lado del otro.

Dos casillas pertenecen a la misma área si hay un camino entre ellos donde cada casilla es del mismo color y se mueve horizontal y verticalmente. Su tarea es contar el número de áreas de la matriz.

Subtareas

• Subtarea 1 (23 puntos): ~1 \le n, m \le 20~, ~1 \le a, b \le 100~.
• Subtarea 2 (24 puntos): ~1 \le n, m \le 20~, ~1 \le a \le 10^9~, ~b = 1~.
• Subtarea 3 (53 puntos): ~1 \le n, m \le 20~, ~1 \le a, b \le 10^9~.

Entrada

La primera línea contiene cuatro números enteros ~n~, ~m~, ~a~ y ~b~.

Las siguientes ~n~ líneas describen la matriz. Cada línea tiene ~m~ caracteres de la ~A~ a la ~Z~ que describen los colores.

Salida

Imprime un único número entero: la cantidad de áreas de la matriz. Como la respuesta puede ser grande, imprímela módulo ~10^9+7~.

Ejemplos

Entrada 1

3 2 4 5
AB
BA
AA

Salida 1

49

La matriz es la siguiente:

ABABABABAB
BABABABABA
AAAAAAAAAA
ABABABABAB
BABABABABA
AAAAAAAAAA
ABABABABAB
BABABABABA
AAAAAAAAAA
ABABABABAB
BABABABABA
AAAAAAAAAA