Ямар нэгэн тэмдэгт мөр нь зөвхөн "0" болон "1"-үүдээс бүтсэн бол түүнийг хоёртын тэмдэгт мөр гэнэ.

Тэмдэгт мөр $v$ нь хоосон биш, мөн тэмдэгт мөр $w$-ийн аль нэгэн байрлалаас эхлэн бүтнээрээ уншигдаж болохоор байвал түүнийг $w$-ийн дэд тэмдэгт мөр гэнэ. Жишээ нь "010" нь "0", "1", "0", "01", "10", "010" гэсэн $6$-н дэд тэмдэгт мөртэй байна. Хоёр дэд тэмдэгт мөр өөр өөр байрлалд оршдог бол тэднийг ялгаатай гэж үзнэ, тиймээс ямар нэгэн тэмдэгт мөр олон дахин орсон байвал тэднийг бүгдийг нь тоолох болно.

Танд хоёртын тэмдэгт мөр $s$ өгөгдсөн бол түүний дотор дотроо яг $k$ ширхэг "1" агуулсан дэд тэмдэгт мөр хэдэн ширхэг байгааг олно уу.

Оролт

Эхний мөрөнд бүхэл тоо $k$ ($0 ≤ k ≤ 10^6$) байх ба хоёрдугаар мөрөнд хоосон биш хоёртын тэмдэгт мөр $s$ байна, $s$-ийн урт $10^6$-н тэмдэгтээс хэтрэхгүй.

Гаралт

Ганцхан бүхэл тоо хэвлэ - өгөгдсөн хоёртын тэмдэгт мөрийн яг $k$ ширхэг "1" агуулсан дэд тэмдэгт мөрүүдийн тоо

C++ хэл дээр 64-битийн тоо хэрэглэх үед %lld-г хэрэглэхгүй байхыг зөвлөж байна. %I64d, эсвэл cin, cout стриймийг ашиглана уу.

In the first sample the sought substrings are: "1$", "1$", "10$", "01$", "10$", "010$".

In the second sample the sought substrings are: "101$", "0101$", "1010$", "01010$".