E. Ангарагчуудын аз

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

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

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

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

Ангарагчууд $k$ суурьтай тооллын систем хэрэглэдэг. $b$ ($0 ≤ b < k$) тоог $азтай тоо$ гэдэг.

Дижитал үндэс $d(x)$ нь ганц оронтой тооноос бүтэх ба $x$ тооны хүрхрээ нийлбэрийг олж байгаа юм. "Хүрхрээ" нийлбэр гэдэг нь цифрүүдийн нийлбэрийг нь нэг оронтой болтол нэмэх юм.

Жишээ нь: $7$ суурьтай тооны хувьд $d(3504_{7}) = d((3 + 5 + 0 + 4)_{7}) = d(15_{7}) = d((1 + 5)_{7}) = d(6_{7}) = 6_{7}$

Хэрвээ тооны дижитал үндэс нь $b$ байвал Ангарагчууд азтай тоонд тооцдог.

Танд $k$ суурьтай тооллын систем дээр $n$ урттай $s$ string өгнө. Таны олох зүйл бол өгөгдсөн string -ийн ялгаатай дэд string нь азтай тоо байдаг string -уудын тоог олох юм.

$s[i... j]$ ($1 ≤ i ≤ j ≤ n$) тэмдэгт мөр нь $s = a_{1}a_{2}... a_{n}$ тэмдэгт мөрийн дэд тэмдэгт мөр. $s[i_{1}... j_{1}]$ болон $s[i_{2}... j_{2}]$ нь $i_{1} ≠ i_{2}$ эсвэл $j_{1} ≠ j_{2}$ ийм байвал ялгаатай тэмдэгт мөр гэж үзнэ.

Оролт

Эхний мөр $k$, $b$ болон $n$ ($2 ≤ k ≤ 10^{9}$, $0 ≤ b < k$, $1 ≤ n ≤ 10^{5}$)

Хоёр дох мөр нь $s$ тэмдэгт мөрийг илэрхийлэх $n$ ширхэг тоо. $a_{i}$ ($0 ≤ a_{i} < k$)

Гаралт

Азтай дэд тэмдэгт мөрүүдийн тоо болох ганц тоо.

C++ дээр cin, cout streams эсвэл %I64d ашиглана уу.

Орчуулсан: anhaabc

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

Оролт
10 5 6
3 2 0 5 6 1
Гаралт
5
Оролт
7 6 4
3 5 0 4
Гаралт
1
Оролт
257 0 3
0 0 256
Гаралт
3

Тэмдэглэл

Эхний жишээний хувьд: $s[1... 2]$ = "3 2", $s[1... 3]$ = "3 2 0", $s[3... 4]$ = "0 5", $s[4... 4]$ = "5" болон $s[2... 6]$ = "2 0 5 6 1".

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