题目描述

黑板上写有 $N$ 个非负整数 $A_1,\, \ldots,\, A_N$。

すぬけ君可以按任意顺序，最多进行 $K$ 次如下两种操作之一：

• 操作 A：将黑板上所有整数都替换为用 $2$ 整除后的结果（向下取整）。
• 操作 B：把黑板上所有整数都减去 $1$。但如果黑板上有 $0$ 出现，则不能进行此操作。

请你求出经过任意次数的操作后，黑板上可能出现的所有不同整数排列有多少种，并对 $1\,000\,000\,007$ 取模。

输入格式

输入为一行，格式如下：

$N$ $K$ $A_1$ $A_2$ $\cdots$ $A_N$

输出格式

输出一个整数，表示通过任意操作后，黑板上整数排列所有可能的不同方案数，对 $1\,000\,000\,007$ 取模。

样例 1

输入

2 2
5 7

输出

6

样例 2

输入

3 4
10 13 22

输出

20

样例 3

输入

1 100
10

输出

11

样例 4

输入

10 123456789012345678
228344079825412349 478465001534875275 398048921164061989 329102208281783917 779698519704384319 617456682030809556 561259383338846380 254083246422083141 458181156833851984 502254767369499613

输出

164286011

说明/提示

限制条件

• $1 \leq N \leq 200$
• $1 \leq A_i \leq 10^{18}$
• $1 \leq K \leq 10^{18}$
• $A_i,\ K$ 均为整数

样例解释 1

所有可能出现的黑板上的整数排列为：$(1,\,1),\ (1,\,2),\ (2,\,3),\ (3,\,5),\ (4,\,6),\ (5,\,7)$，共有 $6$ 种。例如 $(1,\,2)$ 可以通过依次执行操作A、操作B得到。

由 ChatGPT 5 翻译