CSES - Datatähti 2022 alku - Ositus
  • Language:
  • Time limit: 1.00 s
  • Memory limit: 512 MB

Tehtäväsi on laskea, monellako tavalla merkkijono voidaan jakaa osiin niin, että missään osassa ei esiinny kahta samaa merkkiä.

Esimerkiksi kun merkkijono on abac, mahdolliset jaot ovat:

  • a+b+a+c
  • a+b+ac
  • a+ba+c
  • a+bac
  • ab+a+c
  • ab+ac

Koska tehtävän vastaus voi olla suuri luku, tulosta vastaus modulo 10^9+7 eli vastauksen jakojäännös luvulla 10^9+7.

Syöte

Syötteen ainoalla rivillä on merkkijono, jossa on n merkkiä ja joka muodostuu merkeistä az.

Tuloste

Tulosta yksi kokonaisluku: tehtävän vastaus modulo 10^9+7.

Esimerkki

Syöte:

aybabtu

Tuloste:

44

Osatehtävä 1 (40 pistettä)

  • 1 \le n \le 10

Osatehtävä 2 (25 pistettä)

  • 1 \le n \le 100

Osatehtävä 3 (35 pistettä)

  • 1 \le n \le 10^6