Rearrangement of Power-of-Two Sequence

Given a sequence \(a\) of length \(n\) in which every element is a power of two, and an integer \(x\), you are required to rearrange the sequence by choosing a permutation \(p\). The new sequence \(a'\) is defined by \(a'_i = a_{p_i}\), and it must satisfy the condition that for every index \(i\) (\(1 \le i < n\)),

\(a'_i + a'_{i+1} \le x\)

Count the number of valid rearrangements. Two rearrangements are considered different if the permutation \(p\) is different.

Note: You may assume that \(n\) is small (e.g. \(n \le 16\)) so that a backtracking or bitmask dynamic programming solution is feasible.

inputFormat

The first line contains two integers \(n\) and \(x\).

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\), each of which is a power of two.

outputFormat

Output a single integer: the number of valid rearrangements of the sequence.

sample

3 3
1 1 2

6