U263874 线段数

$$我和一具尸体有什么区别？$$ $$你有一颗温热的心脏。$$ $$我们要去哪？$$ $$乐园。$$  你正在摸鱼，可是老师来了，你必须做一道题掩盖一下

我们定义一个数每个长度为 $d$ 的子串中的数字之和不超过 $k$ 的数为线段数 当 $d=1$ 与 $k=2$ 时 $111$ 为线段数 $311$ 不为线段数，因为其第一个长度为 $d$ 的子串大于 $k$ 给出 $a$,$b$,$d$,$k$,求出 $a$,$b$ 之间（包含 $a,b$ ）有多少个线段数

输入共一行 $a,b,d,k$四个整数

输出共一行 表示$a$,$b$ 之间线段数个数

$1 \leq a,b \leq 10^{18}$ $0 \leq k \leq 50$ $1 \leq d \leq min(lg(b)+1,5)$