题目背景

机房的巡检记录是一串整数，每个整数记着一次自检时点亮的指示灯：二进制下第 $b$ 位为 $1$ 表示第 $b$ 号灯当时是亮的。值班员要挑出一段连续的记录，要求这段时间里 $0$ 号灯到 $k-1$ 号灯都亮过。他想知道这样的连续段一共有多少段。

题目描述

给定 $n$ 个非负整数 $a_1, a_2, \dots, a_n$ 与整数 $k$。

对于区间 $[l, r]$（$1 \le l \le r \le n$），把 $a_l, a_{l+1}, \dots, a_r$ 全部按位或起来，得到结果 $S$。如果 $S$ 的二进制表示中第 $0$ 位到第 $k-1$ 位全都是 $1$，就称这个区间是齐全的。

请求出齐全区间的个数。

输入格式

第一行两个整数 $n, k$。

第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$。

输出格式

一行一个整数，表示齐全区间的个数。

输入输出样例 #1

输入 #1

3 2
1 2 3

输出 #1

4

输入输出样例 #2

输入 #2

2 3
1 2

输出 #2

0

输入输出样例 #3

输入 #3

4 1
0 1 0 1

输出 #3

8

说明

样例解释

样例 1 共有 $6$ 个区间。单个数的区间中，$a_1 = 1$ 只有第 $0$ 位是 $1$，$a_2 = 2$ 只有第 $1$ 位是 $1$，都不齐全；$a_3 = 3$ 两位都是 $1$，齐全。三个更长区间的按位或都是 $3$，也都齐全。所以答案是 $4$。

样例 2 中两个数的按位或结果是 $3$，第 $2$ 位始终是 $0$，$k = 3$ 时任何区间都不齐全。

样例 3 中共有 $10$ 个区间，只有 $[1,1]$ 与 $[3,3]$ 的按位或为 $0$（第 $0$ 位不是 $1$），其余 $8$ 个区间都包含至少一个 $1$，因此答案 $8$。

数据范围

• 对于 $30\%$ 的数据，$n \le 300$，$k \le 5$；
• 对于 $60\%$ 的数据，$n \le 5000$；
• 对于 $100\%$ 的数据，$1 \le n \le 2 \times 10^5$，$1 \le k \le 30$，$0 \le a_i < 2^{30}$。