D. Битониксийн эргүүл

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

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

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

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

Байтлэнд Бит-Икс гариг дээр сансрын даалгавар илгээх гэж байна. Бит-Иксийн сансрын хүчний тэргүүлэгч Ахмад Битоникс гаригийн орбитод байнга харуул хийж байдаг учир тэдний ажил хүндрэлтэй болсон.

Бит-Иксийг тойроод цагийн зүүний дагуу $1$-c $n$ хүртэл дугаарлагдсан $n$ станц байна. Станцууд тойрог хэлбэрийн орбитод ижил зайтайгаар байрласан ба $i$ ба $i + 1$ $(1 ≤ i < n)$ болон 1 ба $n$ дугаартай станцууд нь хөрш байна. Хөрш станц бүрийн хоорондох зайнууд хоорондоо тэнцүү ба тус бүр нь сансарын $m$ миллтэй тэнцүү. Эргүүлд гарахын тулд Ахмад Битоникс нэг станцаас пуужиндаа суугаад тойргоор нисэх ба өөр станцад буухаасаа өмнө ядаж нэг сансрын милл зай туулна.

Битониксийн пуужин нь түлшний савнууд дахь түлшний шаталтаар ниснэ. Битоникс $x$ литр түлшний савыг угсраад чиглэлээ сонгоно (цагийн зүүний дагуу эсвэл эсрэг), тэгээд пуужин сонгогдсон чиглэлд тойрог орбитийн дагуу сансрын яг $x$ милл зайд ниснэ. Пуужинд тоормоз байхгүй ба шатахууны сав хоосрохоос өмнө пуужинг зогсоох боломжгүй.

Жишээлбэл $n = 3$ ба $m = 60$ гэж үзье, мөн Битониксд 10, 60, 90 ба 100 литрийн эзэлхүүнтэй шатахууны савнууд байгаа. Хэрвээ Битоникс 1 дугаартай станцаас эхлэсэн ба 100 литрийн шатахууны савыг цагийн зүүний дагуу явахад ашигласан, тэгээд 90 литрийн шатахууны савыг цагийн зүүний дагуу явахад ашигласан мөн 10 литрийн шатахууны савыг цагийн зүүний эсрэг явахад ашигласан гэвэл тэр буцаад 1 дугаартай станцад ирнэ. Энэ нь хүчинтэй эргүүлд тооцогдоно. Битоникс бүх шатахууны савыг ашиглах шаардлагагүй. Энэ жишээн дээр Битониксд өөр нэг боломж байгаа нь ердөө 60 литрийн шатахууны савыг ашиглан 2 эсвэл 3 дугаартай станцруу нисэх юм.

Гэсэн ч хэрвээ $n$ нь 3 мөн $m$ нь 60 байсан бол Битоникс зөвхөн 100 литрийн болон 10 литрийн шатахууны нэг нэг сав байсан бол түүнд хүчинтэй эргүүл хийх боломж байхгүй (тэр ямар ч эргүүлээ яг станц дээр дуусгах боломжгүй.).

Байтлэндийн сансрын агентлаг Ахмад Битониксийн зарим шатахууны савыг устгахыг хүсч байгаа ба тэр хүчинтэй эргүүл хийх боломжгүй болох юм. Ахмад Битониксийг эргүүл хийх боломжгүй болгоход агентлагийн устгах шатахууны савнуудын хэдэн ялгаатай дэд бүрдэл байгааг олж $1000000007$ $(10^{9} + 7)$ тоонд хуваагаад үлдэгдлийг хэвлэнэ үү.

Оролт

Оролтын эхний мөрөнд гурван бүхэл тоо $n$ ($2 ≤ n ≤ 1000$), $m$ ($1 ≤ m ≤ 120$), $t$ ($1 ≤ t ≤ 10000$) байх ба харгалзан станцуудын тоо, хөрш станцуудын хоорондох зай, Ахмад Битониксийн шатахууны савнуудын тоо байна.

Оролтын хоёр дахь мөрөнд зайгаар тусгаарлагдсан $t$ бүхэл тоон утга байх буюу Битониксийн шатахууны савнуудын эзэлхүүнийг илэрхийлэх $1$-с $10^{9}$ хүртэлх тоо байна.

Гаралт

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

Орчуулсан: Г.Мэндбаяр

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

Оролт
7 6 5
5 4 12 6 5
Гаралт
6
Оролт
3 60 2
10 100
Гаралт
4

Тэмдэглэл

Ижилхэн хэмжээтэй байсан ч бүх шатахууны сав ялгаатай.

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