Streaming Sum Modulo K

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem Statement

Given n nonnegative integers and positive k, print the remainder of their sum modulo k, maintaining only a running remainder.

Input

First n and k, followed by exactly n nonnegative integers.

Output

Print the sum modulo k; output 0 when n=0.

Subtasks

• Subtask 1 (20%): n ≤ 20, k,a_i ≤ 100.

• Subtask 2 (30%): n ≤ 1000, k,a_i ≤ 10^6.

• Subtask 3 (50%): n ≤ 100000, k,a_i ≤ 10^9.

Examples

Example 1

Input:

3 7
6 6 6

Output:

4

Explanation: 6+6+6=18 and its remainder modulo 7 is 4.

Example 2

Input:

0 1

Output:

0

Explanation: An empty sum is zero.