You are given an array $A$ of size $N.$ You are also given an integer $K.$

Find the total number of subsets of A such the the LCM of the elements in each subset is divisible by $K.$

Note:

LCM of two integers $P$ and $Q,$ is the smallest positive integer that is divisible by both $P$ and $Q.$

Input Format

The first line contains an integer, $N,$ denoting the number of elements in $A.$

The next line contains an integer, $K,$ denoting the given integer.

Each line $i$ of the $N$ subsequent lines $($where $0i$