Arithmetic Sequence Insertion Game

Given an arithmetic sequence x of length n with first term a and common difference d, you can perform the following operation any number of times:

• Select two distinct elements \(x_i\) and \(x_j\) such that:
• Their sum \(x_i+x_j\) is even.
• The number \(\frac{x_i+x_j}{2}\) is not already in the sequence.
• Then, add \(\frac{x_i+x_j}{2}\) to the sequence. Note that newly added numbers can be used in subsequent operations.

Your task is to determine the maximum number of operations that can be performed.

Observation:

• If d is odd, then for any two numbers \(x_i = a+i\,d\) and \(x_j = a+j\,d\) (with appropriate indices), the condition that \(x_i+x_j\) is even forces \(i+j\) to be even. In this case, it turns out that the calculated midpoint \(\frac{x_i+x_j}{2}\) always belongs to the original sequence. Hence, no operations can be performed.
• If d is even, then notice that every term in the sequence can be written in the form \(a + k\,(d)\), and the sequence only contains numbers congruent to a mod d. In fact, these numbers correspond to every other term in the full sequence with common difference \(\frac{d}{2}\). The missing numbers (which are the potential numbers to be added) are exactly the ones between the existing terms. It can be shown that the maximum number of operations in this case is n - 1.
• Also, when d = 0 or n < 2, no operation is possible because any two selected elements have the same value and thus their average is already present.

Input/Output Summary:

You are given three integers n, a, and d. If d is even and n ≥ 2, output n - 1; otherwise, output 0.

inputFormat

The input consists of a single line containing three space-separated integers:

n a d

where:

• n is the length of the arithmetic sequence.
• a is the first term of the sequence.
• d is the common difference.

outputFormat

Output a single integer representing the maximum number of operations that can be performed.

sample

3 1 2

2