E. Ярослав ба Эрэмбэлэлт

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

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

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

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

Хэрвээ $r$ ширхэг бүхэл тоонуудаас тогтсон $a_{1}, a_{2}, ..., a_{r}$ массив дараах нөхцлүүдийг хангаж байвал Ярослав үүнийг сайн массив гэж нэрлэдэг. Үүнд: $|a_{1} - a_{2}| = 1, |a_{2} - a_{3}| = 1, ..., |a_{r - 1} - a_{r}| = 1, |a_{r} - a_{1}| = 1$, энэ үед .

Хэрвээ $b_{1}, b_{2}, ..., b_{r}$ бүхэл тоонуудтай массив дараах нөхцлүүдийг хангаж байвал онц массив гэж нэрлэнэ. Үүнд:

  1. Элементүүд нь үл буурахаар $(b_{i} ≤ b_{i + 1})$ бол.
  2. Хэрвээ $1 ≤ r ≤ n$ ба $1 ≤ b_{i} ≤ m$ тэнцэтгэл бишүүдийг хангадаг бол.
  3. Хэрвээ бид энэ элементүүдийг дахин эрэмбэлж чадвал хамгийн багадаа нэг, хамгийн ихдээ $k$ ялгаатай сайн массив гаргаж авч чаддаг бол.

Ярославд гурван бүхэл $n, m, k$ тоонууд байгаа. Тэр онц массивын тоонуудыг тоолох хэрэгтэй. Ярославд туслана уу! Хариулт нь их байж болох учир $1000000007$ $(10^{9} + 7)$-д хуваасны дараах үлдсэн хэсгийг нь хэвлэнэ.

Хэрвээ хоёр массивын тухайн байрлалд ялгаатай тоонууд байгаа бол тэдгээрийг ялгаатай гэж үзнэ.

Оролт

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

Гаралт

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

Орчуулсан: Даариймаа

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

Оролт
1 1 1
Гаралт
0
Оролт
3 3 3
Гаралт
2
Сэтгэгдлүүдийг ачааллаж байна...