Given a sequence of N integers a1, a2, ..., aN, any contiguous segment of elements in the original sequence is called a subarray. Two subarrays are considered different if there exists at least one element that belongs to one subarray but not the other.↵
↵
For example, in the sequence {a1, a2, a3, a4}, the subarrays are:↵
{a1}, {a2}, {a3}, {a4}, {a1, a2}, {a2, a3}, {a3, a4}, {a1, a2, a3}, {a2, a3, a4}, {a1, a2, a3, a4}.↵
↵
The task is to count the number of subarrays such that the sum of the M-th powers of the elements in the subarray is divisible by K.↵
first line : N,M,K (1 ≤ N ≤ 10^5; 1 ≤ M ≤10^18,1 ≤ K ≤ 10^5)↵
second line : a1,a2,..an (1 ≤ ai ≤ 10^50)↵
↵
inp: out↵
4 1 3 4↵
3 2 1 5↵
↵
For example, in the sequence {a1, a2, a3, a4}, the subarrays are:↵
{a1}, {a2}, {a3}, {a4}, {a1, a2}, {a2, a3}, {a3, a4}, {a1, a2, a3}, {a2, a3, a4}, {a1, a2, a3, a4}.↵
↵
The task is to count the number of subarrays such that the sum of the M-th powers of the elements in the subarray is divisible by K.↵
first line : N,M,K (1 ≤ N ≤ 10^5; 1 ≤ M ≤10^18,1 ≤ K ≤ 10^5)↵
second line : a1,a2,..an (1 ≤ ai ≤ 10^50)↵
inp: out↵
4 1 3 4↵
3 2 1 5↵
