B. Маш олон тэмдэгт мөрүүд

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

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

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

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

Сануулах үүднээс энэ өвөл Нводскд их хүйтэн байна! Гадаа хүйтэн учир гэрээсээ гаралгүй удсан зарим нэгэн хүн инээдтэй зүйл бодож олжээ. Жишээ нь: яг $n$ урттай $m$ төрлийн үсэгнээс бүтсэн тэмдэгт мөрүүдийн тоог хайж үзье. Гэхдээ эн тэмдэгт мөрүүдийн $k$ урттай дэд тэмдэгт мөр болгон палиндром байх ёстой. Тийм бол нийт хэдэн ширхэг ийм тэмдэгт мөр байх боломжтой вэ? Эдгээр тэмдэгт мөрнүүдийн нийт тоог $1000000007$-д ($10^{9} + 7$) хуваасан үлдэгдлийг олно уу.

Аль ч талаасаа ижил уншигддаг буюу зүүнээсээ баруун руу болон баруунаас зүүн рүү ижил уншигддаг тэмдэгт мөрнүүдийг палиндром гэж нэрлэдэг.

Оролт

Нэг мөрөнд гурван ширхэг бүхэл тоо $n$, $m$, $k$ ($1 ≤ n, m, k ≤ 2000$) өгөгдөнө.

Гаралт

Нөхцлийг хангах тэмдэгт мөрүүдийн тоог $1000000007$-д ($10^{9} + 7$) хуваагаад гарах үлдэгдлийг хэвлэнэ.

Орчуулсан: Энхлут

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

Оролт
1 1 1
Гаралт
1
Оролт
5 2 4
Гаралт
2

Тэмдэглэл

Эхний жишээнд ганцхан $a$ гэсэн тэмдэгт мөр байх боломжтой (хэрэглэх боломжтой ганц л $a$ гэсэн үсэг байна гэж үзье).

Хоёр дахь жишээнд (ашиглах боломжтой нийт үсэгнүүдийг "a" болон "b" гэж үзвэл) дараах тэмдэгт мөрнүүд байх боломжтой: "aaaaa" болон "bbbbb".

Сэтгэгдлүүдийг ачааллаж байна...