4. 数字段

【题目描述】

给定一个长度为$n$的数字序列$a$（每个元素 $a_i$=0或1或...或9），以及三个正整数$m,k,L$。对于连续子序列 $a_l...a_r$，定义其权值$val(l,r) 为将 a_l,...,a_r$按顺序拼接成的十进制数对$m$取模的结果。请计算满足$val(l,r)=k$的连续子序列（长度小于等于$L$）的数量。

输入：/upload/file/20260108/20260108210845_91865.txt

输出：/upload/file/20260108/20260108210854_18581.txt

【输入格式】

第一行包含四个整数$n,m,k,L$。

第二行包含$n$个整数，表示数字序列$a_1,a_2,...,a_n$。

【输出格式】

输出一个整数，表示满足条件的连续子序列的数量。

【样例输入】

3 5 3 2
2 3 1

【样例输出】

2

【数据规模与约定】

对于30%的数据，$n≤1000，L≤1000，m≤100$

对于80%的数据，$n≤5×10^4，L≤10^5，m≤200$

对于90%的数据，$n≤10^5，L≤10^5，m≤800$

对于100%的数据，$n≤10^5，L≤10^5，m≤10^3，k≤10^3$

注意常数问题