Monster Weapon Combinations

Monsters have invaded Earth! In order to fight them, humanity has arranged n weapons in sequence. The i^th weapon has an attack power of \(a_i\), and when used alone, deals \(a_i\) damage.

The weapons are fixed in order, so their sequence cannot be altered. A weapon can be used by itself or combined with adjacent weapons to perform an attack. Specifically, during an attack you can choose a contiguous segment of weapons (which may consist of just one weapon) and the resulting damage will be the sum of the attack powers in that segment.

The alien monster is protected by an invincible shield, immune to any damage. However, it was discovered during battle that the shield breaks whenever it receives damage equal to \(k\) or any multiple of \(k\) (i.e. \(k, 2k, 3k, \dots\)).

Your task is to count the number of ways to choose a contiguous segment of weapons (i.e. a subarray) such that the total damage is a multiple of \(k\).

inputFormat

The first line contains two integers \(n\) and \(k\) (\(1 \leq n \leq 10^5\), \(1 \leq k \leq 10^9\)), representing the number of weapons and the critical damage divisor respectively.

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) (\(0 \leq a_i \leq 10^9\)), representing the attack power of each weapon in order.

outputFormat

Output a single integer: the number of contiguous subarrays (weapon combinations) whose sum is divisible by \(k\>.

sample

5 3
1 2 3 4 1

4