Find the number of non-empty subsets of , the sum of whose elements is divisible by . Print your answer modulo .
Input Format
The only line of input contains numbers and separated by single space.
Constraints
Output Format
Print the only number your answer.
Sample Input 0
6 50
Sample Output 0
0
Explanation 0
There are no subsets of such that it's sum is divisible by .
Sample Input 1
10 50
Sample Output 1
21
Explanation 1
There are such subsets, e.g. .