#B3903. [NICA #3] 星空(Hard Version)

[NICA #3] 星空(Hard Version)

题目背景

Easy Version 和 Hard Version 差别在于数据范围。

题目描述

小 R 有一个长度为 nn 的序列 aa,保证序列中的每个数都是 22 的整数次幂。

小 M 有一个数 xx,她希望重新排列序列 aa,使得不存在一个 i[1,n)i\in[1,n) 满足 ai+ai+1>xa_i+a_{i+1}>x。重排的方式为:选择一个 1n1\sim n 的排列 pp,然后令新序列 aa' 满足 ai=apia'_i=a_{p_i}aa' 即为重排后的序列。

现在你想要知道有多少种重排的方式能满足小 M 的要求。两种重排方式不同当且仅当选择的排列 pp 不同。

输入格式

第一行输入两个正整数 n,xn,x,表示序列长度和小 M 想的那个数;

第二行输入 nn 个正整数 aia_i,表示序列;

输出格式

输出一行表示答案。答案对 109+710^9+7 取模。

6 46
4 8 8 16 32 32
144

提示

数据保证,2n1052 \leq n \leq 10^51ai2601 \leq a_i \leq 2^{60}1x<2631 \leq x < 2^{63}