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