时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
构造一个整数数组
，数组下标从
开始，每个位置只能由
的整数组成, 数字d在数组中出现的次数为
。
给定三个整数l, r , d，求出所有数组长度在[l, r]中数字
的贡献
的和，答案对
取模。
所构造的数组合法：仅当
且 数组长度在
范围内。
两种方案认为不同：仅当两数组组成的序列不同
。
形式上求出：
输入描述:
第一行为一个整数 
，有 组测试数据。
)
每组测试数据有三个正整数 )
和 )
。
输出描述:
对于每组输入，输出一个整数，表示答案,答案对 取模。