Counting Subarrays with Integer Average in an Arithmetic Progression

Given an arithmetic progression of n positive integers: \(a_1, a_2, \ldots, a_n\), where the first term is \(k\) and the common difference is \(d\) (both \(k\) and \(d\) are positive integers), you are required to count the number of contiguous non-empty subarrays (i.e. segments) \((a_l, \ldots, a_r)\) (with \(1 \le l \le r \le n\)) such that the average of the elements in the subarray is an integer.

Note: The subarray's average is defined as \(\frac{a_l + a_{l+1} + \cdots + a_r}{r-l+1}\). It is guaranteed that the sequence forms an arithmetic progression.

Hint: For an arithmetic progression, the average of a contiguous segment is \(\frac{a_l + a_r}{2}\). Thus, the average is an integer if and only if \(a_l + a_r\) is even. Given \(a_l = k + (l-1)d\) and \(a_r = k + (r-1)d\), we derive:

[ a_l + a_r = 2k + (l + r - 2)d. ]

If \(d\) is even, then \((l+r-2)d\) is even and the average will always be an integer. When \(d\) is odd, the condition reduces to \(l + r\) being even (i.e. \(l\) and \(r\) must have the same parity).

Your task is to compute this number efficiently since \(n\) can be very large.

inputFormat

The input consists of a single line containing three space-separated integers \(n\), \(k\), and \(d\), where \(n\) is the length of the sequence, \(k\) is the first element, and \(d\) is the common difference.

outputFormat

Output a single integer, the number of contiguous subarrays which have an integer average.

sample

5 1 2

15