Gốc chữ số

Xét hệ đếm cơ số $k$. Gốc chữ số $d(x)$ của một số $x$ được định nghĩa như sau: cộng tất cả các chữ số của $x$ trong hệ cơ số $k$; nếu tổng thu được vẫn có nhiều hơn một chữ số thì lại cộng tiếp các chữ số của tổng đó, lặp lại cho đến khi nhận được một số chỉ gồm đúng một chữ số. Số một chữ số cuối cùng đó chính là $d(x)$.

Ví dụ với $k=7$: $d({3504}_7)=d((3+5+0+4{)}_7)=d({15}_7)=d((1+5{)}_7)=d(6_7)=6_7$.

Cho một chữ số $b$ với $0\le b<k$. Một số được gọi là may mắn nếu gốc chữ số của nó bằng $b$.

Bạn có xâu $s=a_1{a}_2\dots a_n$ gồm $n$ chữ số trong hệ cơ số $k$. Hãy đếm số cặp chỉ số $(i,j)$ với $1\le i\le j\le n$ sao cho xâu con $s[i..j]=a_i{a}_{i+1}\dots a_j$, đọc như một số trong hệ cơ số $k$, là số may mắn.

Các chữ số $0$ đứng đầu được chấp nhận. Riêng xâu con chỉ gồm toàn chữ số $0$ biểu diễn số $0$, và theo định nghĩa $d(0)=0$.

Hai xâu con $s[i_1..j_1]$ và $s[i_2..j_2]$ được coi là khác nhau nếu $i_1\ne i_2$ hoặc $j_1\ne j_2$, kể cả khi chúng gồm cùng một dãy chữ số.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $k$, $b$ và $n$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$ cách nhau bởi dấu cách, trong đó $a_i$ là chữ số thứ $i$ của xâu $s$ trong hệ cơ số $k$.

Dữ liệu ra

In ra một số nguyên duy nhất là số xâu con của $s$ biểu diễn số may mắn.

Ràng buộc

• $2\le k\le {10}^9$
• $0\le b<k$
• $1\le n\le {10}^5$
• $0\le a_i<k$

Ví dụ