CSES - Datatähti 2020 loppu - Alueet
  • Time limit: 1.00 s
  • Memory limit: 512 MB

Sinulle annetaan n×mn \times m -ruudukko, jonka jokaisella ruudulla on väri. Tämän pohjalta muodostetaan na×mbna \times mb -ruudukko asettamalla alkuperäisen ruudukon kopioita aa kertaa allekkain ja bb 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 nn, mm, aa ja bb.

Seuraavat nn riviä kuvaavat ruudukon. Jokaisella rivillä on mm 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 109+710^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ä)

  • 1n,m201\le n, m\le 20
  • 1a,b1001\le a, b \le 100

Osatehtävä 2 (24 pistettä)

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

Osatehtävä 3 (53 pistettä)

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