Jeetu enjoys solving number theory problems.He is stuck in a problem, so he wants help with this problem about multiplying integers and modulo operation!
Jeetu's favourite integer is t, and he has a sequence of n integers in front of him, called a1, a2, ..., an.
He calls a pair of positive integers (x, y) good pair if 1 <= x<= y <= n, and (axax+1...ay) mod t = 1 . Help Kevin find the number of good pairs!
Input
The input consists of n+1 lines.
The first line contains 2 integers: n and t. The next n lines each contain an integer, the sequence: a1, a2, ..., an.
Output
The output is a single integer, the number of good pairs.
Constraints
2 <= t <= 10^9. 1 <= n <= 10^5. 1 <= ai <= 10^9.
The good pairs are (1, 2), (1, 3) and (3, 3). The numbers in these ranges multiply to 1 (mod 6).
