- Time limit: 1.00 s
- Memory limit: 512 MB
Sinulle annetaan -ruudukko, jonka jokaisella ruudulla on väri. Tämän pohjalta muodostetaan -ruudukko asettamalla alkuperäisen ruudukon kopioita kertaa allekkain ja 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 , , ja .
Seuraavat riviä kuvaavat ruudukon. Jokaisella rivillä on 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 .
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