D. Үг хуваасан нь

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

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

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

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

Нэгэн сонирхолтой үгийн тоглоом тоглоцгооё. Энэ тоглоомонд тусгай үйлдлийн тусламжтайгаар ямар нэг үгийг өөр үг болгон хувиргадаг юм.

Бидэнд $w$ үг өгөгдсөн гэж үзье. Тэгвэл энэ үгийг $x$ болон $y$ гэсэн хоосон биш хоёр хэсэгт хуваах бөгөөд үүнийг $w=xy$ гэж тэмдэглэе. Хуваах үйлдэл нь $w=xy$ үгийг $u=yx$ болгон хувиргадаг. Жишээлбэл, "wordcut" гэсэн үгийг хуваах үйлдлийн тусламжтайгаар "cutword" болгон хувиргана.

Танд $start$ ба $end$ гэсэн $2$ үг өгөгдөнө. $start$ үгийг хуваах $k$ тооны дараалсан үйлдлүүдийн тусламжтайгаар $start$ үгийг $end$ болгон хувиргах хэдэн боломж байгааг олоорой.

Хийгдсэн үйлдлийн дараалал нь ялгаатай бол уг $2$ боломжийг ялгаатай гэж үзнэ. Хэрэв эхний дарааллын $i$-р үйлдэлд үгийг $x$ ба $y$ хэсэгт хуваадаг, $2$-р дарааллын $i$-р үйлдэлд үгийг $a$ ба $b$ хэсэгт хуваадаг, мөн $x≠a$ байдаг $i$ ($1≤i≤k$) тоо байдаг бол уг $2$ үйлдлийн дарааллыг ялгаатай гэж үзнэ.

Оролт

Эхний мөрөнд хоосон биш $start$ үг, $2$ дахь мөрөнд хоосон биш $end$ үг өгөгдөнө. Эдгээр үгнүүд нь Латин жижиг үсгүүдээс бүрдсэн байна. $start$ үгний үсгийн тоо $end$ үгний үсгийн тоотой тэнцүү байх ба үг нь хамгийн багадаа $2$ үсэг, ихдээ $1000$ үсэг агуулна.

$3$ дахь мөрөнд хийх үйлдлийн тоог харуулах $k$ ($0≤k≤10^{5}$) бүхэл тоо өгөгдөнө.

Гаралт

Асуултын хариулт болох тоог хэвлээрэй. Энэ тоо нь маш том тоо байж болох учир $1000000007$ $(10^{9} + 7)$-д хуваагаад үлдэгдлийг нь хэвлэнэ үү.

Орчуулсан: Солонго

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

Оролт
ab
ab
2
Гаралт
1
Оролт
ababab
ababab
1
Гаралт
2
Оролт
ab
ba
2
Гаралт
0

Тэмдэглэл

Эхний жишээний боломж нь:

"ab" → "a|b" → "ba" → "b|a" → "ab"

Хоёр дахь жишээний $2$ боломж нь:

  • "ababab" → "abab|ab" → "ababab"
  • "ababab" → "ab|abab" → "ababab"
Сэтгэгдлүүдийг ачааллаж байна...