E. Аня ба шоонууд

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

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

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

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

Аня наах, эвхэх дуртай. Өнөөдөр тэр үүнийг хийхээр шийдсэн юм.

Аняд зүүнээсээ баруун тийш $1$-ээс $n$ хүртэл дугаарлагдсан $n$ ширхэг шоонууд байгаа бөгөөд тэдгээр шоон дээр натурал тоонууд бичсэн байгаа. Мөн түүнд дээрээ анхаарлын тэмдэгтэй $k$ ширхэг наалт байгаа. Наалтнуудын тоо нь шооны тооноос ихгүй гэдгийг бид мэднэ.

Аня шоон дээр анхаарлын тэмдэг наагаад тухайн шоон дээр бичигдсэн тооны факториалийг авч чадна. Жишээлбэл хэрвээ шоон дээр $5$-ын тоо байгаа бол анхаарлын тэмдэг наагаад $5!$ болно, энэ нь $120$-той тэнцүү.

Наалтыг наасны дараа сонгогдсон шоонууд дээр бичигдсэн тоонуудын нийлбэр нь $S$-тэй тэнцүү байхаар хамгийн ихдээ $k$ ширхэг анхаарлын тэмдгийг сонгогдсон шооны зарим дээр наана. Та Аняд шоонуудаас сонголт хийх хэдэн арга байгааг тоолоход туслах хэрэгтэй. Аня шоо бүр дээр хамгийн ихдээ нэг ширхэг анхаарлын тэмдэг нааж чадна. Та үүнийг хийж чадах уу?

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

Оролт

Оролтын эхний мөрөнд зайгаар тусгаарлагдсан $n$, $k$, $S$ ($1 ≤ n ≤ 25$, $0 ≤ k ≤ n$, $1 ≤ S ≤ 10^{16}$) гурван бүхэл тоог оруулна. Эдгээр нь шоонуудын тоо, наалтуудын тоо болон түүний авах хэрэгтэй нийлбэр юм.

Хоёр дахь мөрөнд $n$ ширхэг $a_{i}$ ($1 ≤ a_{i} ≤ 10^{9}$) эерэг бүхэл тоонууд байна. Эдгээр нь шоонууд дээр бичигдсэн тоонууд юм. Зүүнээс баруун тийш нэгээс эхлэн дугаарлана.

Олон шоон дээр ижил тоо байж болно.

Гаралт

Тоонуудын нийлбэр нь өгөгдсөн $S$ тоотой тэнцүү байхаар сонгогдсон шоонудын зарим дээр нь анхаарлын тэмдэг наах бөгөөд шоонуудаас сонголт хийх хэдэн арга байгааг хэвлэнэ.

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

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

Оролт
2 2 30
4 3
Гаралт
1
Оролт
2 2 7
4 3
Гаралт
1
Оролт
3 1 1
1 1 1
Гаралт
6

Тэмдэглэл

Эхний жишээнд хоёр шоог хоёуланг нь сонгох ганцхан арга байгаа бөгөөд тэдгээр дээр анхаарлын тэмдэгтэй наалт наана.

Хоёр дахь жишээнд хоёр шоог хоёуланг нь сонгох ганцхан арга байгаа боловч тэдгээр хоёр шоон дээр хоёулан дээр нь анхаарлын тэмдэгтэй наалт нааж болохгүй.

Гурав дахь жишээнд шоонуудаас сонгох гурван арга байна. Мөн сонгосон шоо бүр дээрээ анхаарлын тэмдэг наах эсвэл наахгүй байх боломжтой. Тиймээс нийт зургаан арга байна.

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