时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
Grammy has a favorite number 
. She thinks that all the numbers divisible by are good.
For each array containing only numbers from
to 
, Grammy define its goodness as the number of non-empty consecutive subarrays that sums to a good number.
Please count the number of arrays of length
such that its goodness is 
. Since the answer can be enormous, output the answer modulo 
.
For each array containing only numbers from
Please count the number of arrays of length
输入描述:
A single line contains three integers(
).
输出描述:
Output a single number, denoting the answer modulo