D. Гэмт хэргийн менежмент

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

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

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

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

Зеяд Египетэд шийтгэл хүлээхгүйгээр $n$ гэмт хэрэг үйлдэхийг хүсдэг. Хэд хэдэн төрлийн гэмт хэргүүд байдаг. Жишээ нь: хээл хахууль нь гэмт хэрэгт тооцогддог боловч 2 удаа давтан үйлдэхэд гэмт хэрэг гэж үздэггүй. Тиймээс хээл хахуулийг тэгш удаа давтахад энэ нь гэмт хэрэгт тооцогдохгүй. Хурд хэтрүүлэх нь мөн гэмт хэрэг, гэхдээ 5-д хуваагдах удаа үйлдэхэд энэ нь гэмт хэрэг болохгүй.

Илүү тодруулбал, гэмт хэргийн давталтын $c$ нөхцөл мэдэгдэж байгаа.

Нөхцөл бүрд гэмт хэргийн төрөл болох $t_{i}$ ба давталтын тоо болох $m_{i}$ байна. Хэрвээ Зеяд $t_{i}$ гэмт хэргийг $m_{i}$-д хуваагдах удаа үйлдвэл шийтгэл хүлээхгүй. Зарим гэмт хэргүүд нэгээс олон удаа жагсаалтад орж болно. Ийм үед дор хаяж нэг нөхцөл нь биелж байхад тэр шийтгэл хүлээхгүй. Мэдээж ямар нэг гэмт хэргийг үйлдээгүй бол шийтгэл хүлээхгүй.

Зеяд яг $n$ гэмт хэргийг ямар ч шийтгэлгүйгээр хэдэн янзаар үйлдэж болохыг сонирхсон.

Гэмт хэргийг үйлдэх дараалал нь хамаатай. Өөрөөр хэлбэл $w1$ ба $w2$ гэсэн 2 гэмт хэргийн дарааллын хувьд $w1_{i} = w2_{i}$ ($1 ≤ i ≤ n$) байх үед л $n$ гэмт хэрэг нь ижил байна гэж үзнэ.

Оролт

Эхний мөрөнд $n$ ба $c$ ($0 ≤ n ≤ 10^{18}, 0 ≤ c ≤ 1000$) гэсэн 2 бүхэл тоо -- Зеядын хийхийг хүсэж байгаа гэмт хэргийн тоо ба түүний мэдэж байгаа нөхцөлийн тоо.

Дараа нь $c$ нөхцөлийн тайлбар өгөгдөнө. Нийт $26$ төрлийн гэмт хэрэг байна. Нөхцөлийг тодорхойлохдоо гэмт хэргийн төрөл -- Латин цагаан толгойн том үсэг -- ба давталтын тоо өгөгдөнө.

Гэмт хэрэг бүрийн давталт нь эерэг бүхэл тоо байх ба өгсөн бүх давталтын тоонуудын үржвэр $123$-с хэтрэхгүй. Зарим нөхцөлүүд оролтод нэгээс олон удаа давтагдан орж болно.

Гэмт хэргийн давталт нь $1$ байвал хэдэн ч удаа энэ гэмт хэргийг үйлдсэн ямар ч ял шийтгэл хүлээхгүй гэсэн үг. Заримдаа хууль зарлигийг заавал биелүүлэх албагүй байдаг шүү дээ.

Мэдээж хэрэг жагсаалтад ороогүй гэмт хэргийг үйлдвэл гарцаагүй ял шийтгэл хүлээх болно.

С++ дээр 64-битийн бүхэл тоонуудыг унших болон бичихдээ %lld тодорхойлогчийг бүү хэрэглэнэ үү. Үүний оронд cin, cout streams болон %I64d тодорхойлогчийг хэрэглэхийг илүүд үзнэ үү.

Гаралт

Зеяд яг $n$ гэмт хэргийг ямар ч шийтгэлгүйгээр хэдэн янзаар үйлдэж болохыг $12345$ модулиар хэвлэ.

Орчуулсан: Б.Алтангэрэл

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

Оролт
5 2
A 1
B 2
Гаралт
16
Оролт
6 3
A 1
B 2
C 3
Гаралт
113
Оролт
8 3
A 2
A 3
B 2
Гаралт
128

Тэмдэглэл

Эхний жишээн дээр, 16 янзын боломж байна: AAAAA, AAABB, AABAB, AABBA, ABAAB, ABABA, ABBAA, BAAAB, BAABA, BABAA, BBAAA, ABBBB, BABBB, BBABB, BBBAB, BBBBA.

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