U118800 数数

求满足下列条件的正整数数列的个数： - 数列的长度为 $n$ - 数列中的所有数都是 $l$ 到 $r$ 间的整数； - 数列中所有数的和能被 $k$ 整除。

一行，四个正整数：$n, l, r, k$。

一个正整数，即满足条件的数列的数量。答案有可能很大，请输出答案对 $10^9+7$ 取模的值。

**样例解释 1** 数列共有 $3$ 个，分别为：$[1, 2]$，$[2, 1]$，$[3,3]$。 **样例解释 2** 我有一个绝妙的解释，可惜这里地方太小，写不下。 **数据范围** $1 \leq n \leq 10^{18}, 1 \leq l \leq r \leq 10^{18}, 1 \leq k \leq 10^2$