Sinulle annetaan $n \times m$ -ruudukko, jonka jokaisella ruudulla on väri. Tämän pohjalta muodostetaan $na \times mb$ -ruudukko asettamalla alkuperäisen ruudukon kopioita $a$ kertaa allekkain ja $b$ kertaa rinnakkain.

Kaksi ruutua kuuluvat samaan alueeseen, jos niiden välillä on polku, jossa jokainen ruutu on samanvärinen ja liikutaan vaaka- ja pystysuuntaisesti. Tehtäväsi on laskea ruudukon alueiden määrä.

Syöte

Ensimmäisellä rivillä on neljä kokonaislukua $n$, $m$, $a$ ja $b$.

Seuraavat $n$ riviä kuvaavat ruudukon. Jokaisella rivillä on $m$ merkkiä väliltä A–Z, jotka kuvaavat värit.

Tuloste

Tulosta yksi kokonaisluku: ruudukon alueiden määrä. Koska vastaus voi olla suuri, tulosta se modulo $10^9+7$.

Esimerkki

Syöte:

3 2 4 5
AB
BA
AA

Tuloste:

49

Selitys: Ruudukko on seuraava:

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

Osatehtävä 1 (23 pistettä)

• $1\le n, m\le 20$
• $1\le a, b \le 100$

Osatehtävä 2 (24 pistettä)

• $1\le n, m\le 20$
• $1 \le a \le 10^{9}$
• $b = 1$

Osatehtävä 3 (53 pistettä)

• $1\le n, m\le 20$
• $1\le a, b \le 10^9$