Divisibility

Interview

Time limit1sMemory limit128 MB

Summary

Given a sequence and a modulus K, decide whether some choice of + or - before each later element makes the total divisible by K.

Level: Medium5 of 10
Topics: Dynamic programming, Math, Number theory, Implementation
Solved: No attempts yet

Problem

Consider a sequence of integers. By placing a + or - operator between each pair of adjacent integers, you can form many different arithmetic expressions with different values. The first integer's sign is always fixed as +. For example, the sequence 17, 5, -21, 15 yields eight possible expressions:

17 + 5 + -21 + 15 = 16
17 + 5 + -21 - 15 = -14
17 + 5 - -21 + 15 = 58
17 + 5 - -21 - 15 = 28
17 - 5 + -21 + 15 = 6
17 - 5 + -21 - 15 = -24
17 - 5 - -21 + 15 = 48
17 - 5 - -21 - 15 = 18

We say the sequence is divisible by $K$ if + and - operators can be placed so that the resulting value is divisible by $K$ . In the example above, the sequence is divisible by 7 (17 + 5 + -21 - 15 = -14) but not by 5.

Write a program that determines whether a sequence of integers is divisible by $K$ .

Input

The first line contains two integers $N$ and $K$ ( $1 \le N \le 10000$ , $2 \le K \le 100$ ) separated by a space.

The second line contains a sequence of $N$ integers separated by spaces. Each integer has absolute value at most 10000.

Output

Print "Divisible" if the given sequence is divisible by $K$ , or "Not divisible" if it is not.

Examples2

Example 1
Input
```
4 7
17 5 -21 15
```
Expected output
```
Divisible
```
Example 2
Input
```
4 5
17 5 -21 15
```
Expected output
```
Not divisible
```