Magic Set

Katya has a sequence of integers $a_1, a_2, \dots, a_n$ and an integer $m$. She defines a *good* sequence of integers as a non-empty sequence such that the sum of the elements in each of its non-empty subsequences is divisible by $m$. Katya wants to know the number of good subsequences of the sequence $a$. Can you help her? ### Input - The first line of the input contains a single integer $T$ d