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

Input 1

1 10

Output 1

1

Input 2

3 10

Output 2

6

Input 3

4 10

Output 3

0

Input 4

123451234 123451234

Output 4

61725617

Template

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

# print your output