CSES - Datatähti 2020 loppu - Alueet
  • Time limit: 1.00 s
  • Memory limit: 512 MB
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$