Series Sum I

Problem Statement

You are given two integers $n$ and $k$.

You have the following infinite sequence $S = [1 \small\text{ mod } \normalsize k,\ \ \ (1 + 2) \small\text{ mod }\normalsize k,\ \ \ (1 + 2 + 3) \small\text{ mod }\normalsize k,\ ... ]$, in other words $S_i = (\sum_{j=1}^ij) \small\text{ mod }\normalsize k$.

Determine the value of $S_n$, in other words, determine the $n^{th}$ value of the infinite sequence.

Input Format

Your first line will contain three space-separated integers $n$ and $k$ respectively.

Output Format

You should output a single integer $S_n$, the $n^{th}$ integer of $S$ (one-indexed).

Constraints

• $1 \leq n \leq 10^{9}$
• $1 \leq k \leq 10^9$

Sample Cases

1 10

1

3 10

6

4 10

0

123451234 123451234

61725617

Template

n, k = map(int, input().split())

# print your output