Хэрэв $a_{i}$ $(i = 0, 1, ...)$ томъёо тус бүр нь 0 юм уу 1-тэй тэнцүү бол, мөн $n ≥ k$ бүрт болон $a_{n} = c_{1}*a_{n - 1} + c_{2}*a_{n - 2} + ... + c_{k}*a_{n - k} (mod 2), $ гэсэн коэффициентууд байдаг бол $a_{0}, a_{1}, ...$ гэсэн дарааллыг хоёртын рекурент дараалал гэнэ. $c_{i}$ бүр нь бүгд нэгэн зэрэг $0$ биш гэдгийг санаарай.

Энэ мэтийн дарааллыг $k$-хослол ${a_{s}, a_{s + 1}, ..., a_{s + k - 1}}$-ээс ховорхон харж болох ба энэ нь үе үе давтамжтай. Түүнчлэн хэрэв $k$-хослол нь зөвхөн 0 агуулж байвал тус дараалал тэр чигээрээ зөвхөн 0-ийг агуулах учир энэ нь тийм ч сонирхолтой бус байна.
Үгүй бол дарааллын хамгийн бага давтамж нь $2^{k} - 1$-ээс бага байх ба $2^{k} - 1$ гэсэн тэгээс ялгаатай $k$-хослол байна. Хэрэв хамгийн бага давтамж нь яг $2^{k} - 1$ байвал урт дараалал гэж үзье. Та өгөгдсөн $k$-д урт дараалал байгаа эсэхийн олоорой.

Оролт

Оролт нь $k$ ($2 ≤ k ≤ 50$) гэсэн ганц бүхэл тоо агуулна.

Гаралт

Хэрэв тийм урт дараалал байхгүй бол -1 гэж хэвлэ. Үгүй бол гаралтын эхний мөр нь $c_{1}, c_{2}, ..., c_{k}$ коэффициенттой $k$ бүхэл тоо агуулсан байна. Хоёр дахь мөр нь $a_{0}, a_{1}, ..., a_{k - 1}$ дарааллын $k$ гэсэн анхны элементүүд агуулсан байна. Бүх элементүүд, коэффициентууд нь 0 юм уу 1-тэй тэнцүү мөн дор хаяж нэг $c_{i}$ нь 1-тэй тэнцүү байна. Хэрэв хэд хэдэн зөв хариу байвал нэгийг хэвлэнэ үү.

1. Эхний жишээнд: $c_{1} = 1$, $c_{2} = 1$, so $a_{n} = a_{n - 1} + a_{n - 2} (mod 2)$. Иймээс дараалал нь:

Тиймээс үүний давтамж нь $3 = 2^{2} - 1$-тай тэнцүү байна.

2. Хоёр дахь жишээнд: $c_{1} = 0$, $c_{2} = 1$, $c_{3} = 1$, so $a_{n} = a_{n - 2} + a_{n - 3} (mod 2)$. Тиймээс бидний дараалал:

Үүний давтамж нь $7 = 2^{3} - 1$-тэй тэнцүү байна.

Давтамжийг өнгөөр будсан байна.