RoAlgo Contest #6 | sugubatz

Cosmin was bored during the Romanian class when the teacher mentioned a mischievous character in the story "Povestea lui Harap-Alb." This reminded Cosmin of a tricky problem he couldn't solve. If you help him solve the problem, he will send you a mischievous elf with a violin and a bow. Thus, Cosmin will understand how to solve the problem, and you will enjoy harmonious music.

Task

You are given two numbers, $N$ and $X$, followed by an array $A$ of $N$ non-zero natural numbers, indexed from $1$ to $N$. A new array $B$ will be constructed, where each number $b_i$ ($1 \leq i \leq N$) takes the largest value of the greatest common divisor that $a_i$ has with another number in the array $A$. Determine the number of subarrays in array $B$ whose bitwise "OR" sum is greater than or equal to the number $X$.

A subarray of array $B$ is a sequence of elements from different, consecutive positions.

The bitwise "OR" sum of a subarray $v_1, v_2, \dots, v_k$ is defined as $v_1 \vert v_2 \vert \dots \vert v_k$, where $\vert$ signifies the bitwise "OR" operator.

Input data

The first line contains the natural numbers $N$ and $X$, and the second line contains the $N$ natural numbers of the array $A$. The numbers on the same line are separated by a space.

Output data

Print a single number representing the number of subarrays with the desired property.

Constraints and clarifications

• $2 \leq N \leq 1 \ 000 \ 000$
• $1 \leq X \leq 1 \ 000 \ 000$
• $1 \leq a_i \leq 1 \ 000 \ 000$

Note

Due to the very large input data, use the following instructions at the beginning of the main() function in your C++ program:

ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);

Example

stdin

5 3
17 2 9 12 2

stdout

12

Explanation

After each number $b_i$ ($1 \leq i \leq N$) takes the largest value of the greatest common divisor that $a_i$ has with another number in array $A$, the array $B$ has values $1, 2, 3, 3, 2$. In this new array, there are $12$ subarrays that have a bitwise "OR" sum greater than or equal to $3$.