C. Тэмдэгт мөрийн өөр нэгэн бодлого

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

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

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

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

Ямар нэгэн тэмдэгт мөр нь зөвхөн "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 стриймийг ашиглана уу.

Орчуулсан: mmur

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

Оролт
1
1010
Гаралт
6
Оролт
2
01010
Гаралт
4
Оролт
100
01010
Гаралт
0

Тэмдэглэл

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$".

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