### PROBLEM LINK:

**Author:** Full name

**Tester:** Full name

**Editorialist:** Oleksandr Kulkov

### DIFFICULTY:

SIMPLE

### PREREQUISITES:

Basic combinatorics

### PROBLEM:

You have a sequence of integers a_1,a_2,\dots,a_n and an integer m.

Good sequence is an integer sequence such that sum of elements in each of its subsequences is divisible by m.

You have to calculate number of good subsequences of a.

### QUICK EXPLANATION:

Output 2^k-1 where k is number of a_i divisible by m.

### EXPLANATION:

Sequence is good \iff all of its elements are divisible by m. Both implications are obvious: \Longleftarrow follows from the fact that if a and b are divisible by m than a+b is also divisible by m and \implies follows directly from definition of the good sequence. Thus if a_{i_1}, \dots, a_{i_k} is subsequence of all numbers divisible by m, you can use any its subsequence except for the empty one. Thus the answer is 2^k-1 because for each element of this subsequence you will either take it or not and we subtract 1 to not count the case when we don’t take anything.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.