E. Оньсон тоглоомд дурлагч

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Олег Петров нь үгийн сүлжээнд дуртай ба 4-дэх өдөр болгон тэрээр үгийн сүлжээ болон бусад үгийн оньсон тоглоомтой өөрийн дуртай сэтгүүлээ худалдан авдаг. Сүүлийн авсан сэтгүүл дээрээс Олег нэгэн сонирхолтой оньсон тоглоом олсон ба уг сэтгүүл нь оньсыг тайлсан хүнд үнэтэй шагнал амлажээ. Бид уг бодлогын албан ёсны тайлбарыг доор дүрсэлнэ.

Оньсон тоглоомын талбар нь 2 мөрөөс тогтох ба мөр болгон нь $n$ нүдтэй. Нүд болгон нь яг нэг Англи жижиг үсэг агуулна. Танд $w$ үг өгөгдөх ба уг үг нь $k$ ширхэг Англи жижиг үсгүүдээс тогтох юм. Уг оньсон тоглоомын хариу нь тоглоомын нүднүүд $c_{1}$, $...$, $c_{k}$-ын дараалал байх бөгөөд дараах шинж чанартай байна:

  • $1$-ээс $k$ хүртэлх бүх $i$-ын хувьд $c_{i}$ нүдэнд бичигдсэн үсэг нь $w_{i}$ үсэгтэй тохирох ёстой;
  • Дарааллын бүх нүднүүд нь хос хосоороо ялгаатай байна;
  • $1$-ээс $k - 1$ хүртэлх бүх $i$-ын хувьд $c_{i}$ and $c_{i + 1}$ нүднүүд нь ерөнхий талтай байна.

Олег Петров уг оньсон тоглоомын хариуг хурдан олжээ. Одоо тэрээр уг оньсон тоглоомд хэчнээн ялгаатай хариулт байгааг бодож эхэлжээ. Олег Петров их тоонуудад дургүй ба иймд хариултыг $10^{9} + 7$ модулаар бодож хэвлэнэ үү.

Хэрэв нүднүүдийн дарааллууд нь дор хаяж нэг байрлалаараа ялгаатай буюу $c_{j} ≠ c'_{j}$ байх $1$-ээс $k$-хүртэлх ядаж нэг $j$ оршин байвал $c_{i}$ болон $c'_{i}$ 2 дарааллыг ялгаатай хариулт гэж үзнэ.

Оролт

Эхний 2 мөрөнд оньсон тоглоомын талбарын хэлбэр өгөгдөнө. Эдгээр мөрүүд нь хоосон биш байх ба тус бүр нь яг $n$ ширхэг Англи жижиг үсгүүд агуулсан байна.

Дараагийн мөр нь хоосон байна.

Дараагийн мөр нь хоосон биш байх ба $w$ үг агуулна. Уг үг нь Англи жижиг үсгүүдээс тогтсон байна.

Мөр болгоны урт нь $2 000$-оос хэтрэхгүй.

Гаралт

Оньсон тоглоомын ялгаатай хариултын тоог $10^{9} + 7$ модулаар бодсон ганц бүхэл тоог хэвлэнэ үү.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
code
edoc

code
Гаралт
4
Оролт
aaa
aaa

aa
Гаралт
14
Сэтгэгдлүүдийг ачааллаж байна...