因為大獅子很喜歡在生日的時候收到意義不明的禮物，所以他生日的時候收到了\(n\)數字\(a_1, a_2...a_n\)
身為一位魔法少女，大獅子可以對這些數字進行以下兩種操作

1. 把\(a_i\)變成\(a_i^2\)，並消耗1點魔力
2. 把\(a_i\)變成\(2 \times a_i+3\)，並消耗2點魔力
   因為數字接觸到魔力之後就會開始亂跑，所以大獅子只能對每個數字施放至多一次魔法
   大獅子一開始有\(k\)點魔力，魔力值=0時便不能再施展任何魔法
   由於某些不可告人的原因，吃完蛋糕後的大獅子想知道有幾種方法可以讓這串數字和恰能被x整除？
   \(1 \leq n \leq 25\)
   \(0 \leq k \leq 2*n \)
   \(1 \leq x \leq 10^9\)
   \(0 \leq a_i \leq 10^8\)

輸入格式

第一行包括3個數字\(n, k, x\)，\(n\)為有幾個數字，\(k\)為魔力量，\(x\)為要能整除的數 第二行有n個數字，代表大獅子收到的數字

輸出格式

輸出一個數字：有幾種施魔法的方法能令數字和被x整除

範例輸入 1

5 1 5
1 2 3 4 5

範例輸出 1

3

範例輸入 2

5 2 5
1 2 3 4 5

範例輸出 2

5

提示

其實題目靈感是從CF偷來的 原題:https://codeforces.com/contest/525/problem/E