D. Гукиз ба хоёртын үйлдлүүд

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

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

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

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

Гукиз ихэвчлэн массивуудаар тоглодог гэдгийг бид мэднэ. Одоо тэр дараах бодлогын талаар бодож байна:

$2^{l}$-ээс эрс бага, сөрөг биш элементүүдээс тогтсон $n$ урттай, $(a_{1}$ $and$ $a_{2})$ $or$ $(a_{2}$ $and$ $a_{3})$ $or...or$ $(a_{n-1}$ $and$ $a_{n})=k$ нөхцлийг хангадаг $a$ массив хэдэн ширхэг байгаа бол? Энд байгаа and үйлдэл нь битийн AND үйлдлийг илэрхийлнэ (Паскал хэлэнд and үйлдлээр, C/C++/Жава/Пайтон хэлэнд & үйлдлээр илэрхийлэгдэнэ), харин or үйлдэл нь битийн OR үйлдлийг илэрхийлнэ (Паскал хэлэнд or үйлдлээр, C/C++/Жава/Пайтон хэлэнд | үйлдлээр илэрхийлэгдэнэ).

Хариулт хэтэрхий том тоо байж болох тул хариуг $m$ тоонд хуваагаад гарсан үлдэгдлийг хэвлэнэ. Энэ удаад Гукиз ямар ч шийдэл олж чадахгүй байлаа. Тиймээс таны тусламж яг одоо л Гукизд хэрэгтэй!

Оролт

Оролтын нэг мөрөнд $n$, $k$, $l$, $m$ ($2 ≤ n ≤ 10^{18}$, $0 ≤ k ≤ 10^{18}$, $0 ≤ l ≤ 64$, $1 ≤ m ≤ 10^{9} + 7$) дөрвөн бүхэл тоо оруулна.

Гаралт

Нэг мөрөнд дээрх нөхцлийг хангасан массивуудын тоог $m$ тоонд хуваагаад гарсан үлдэгдлийг хэвлэнэ.

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

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

Оролт
2 1 2 10
Гаралт
3
Оролт
2 1 1 3
Гаралт
1
Оролт
3 3 2 10
Гаралт
9

Тэмдэглэл

Эхний жишээнд тохирох массивууд: $(1, 1)$, $(3, 1)$, $(1, 3)$.

Хоёр дахь жишээнд тохирох нэг л массив байна: $(1, 1)$.

Гурав дахь жишээнд тохирох массивууд: $(0, 3, 3)$, $(1, 3, 2)$, $(1, 3, 3)$, $(2, 3, 1)$, $(2, 3, 3)$, $(3, 3, 0)$, $(3, 3, 1)$, $(3, 3, 2)$, $(3, 3, 3)$.

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