集逆态没
时间限制:C/C++/Rust/Pascal 3秒,其他语言6秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

\hspace{15pt}给你四个正整数 n, k, l, r,定义一个非空的非负整数集合 \Bbb S 是「好的」,当且仅当同时满足:
\hspace{23pt}\bullet\,\Bbb S 内的每个元素都被区间 [l, r] 包含;
\hspace{23pt}\bullet\,\Bbb S 中所有元素的按位或是 k 的一个子集。
\hspace{15pt}对所有「好的」集合 \Bbb S,设 f(\Bbb S) 为 \Bbb S 内所有元素按位与的结果,请你求出所有可能的 f(\Bbb S) 取值中,满足 f(\Bbb S) \le n 的不同取值个数。

输入描述:

\hspace{15pt}第一行输入四个正整数 n, k, l, r \left(1 \leq n, k \leq 10^{18};\, 0 \leq l \leq r \leq 10^{18}\right)

输出描述:

\hspace{15pt}输出一个非负整数,表示所有可能的 f(\Bbb S) 取值中,满足 f(\Bbb S) \le n 的不同取值个数。
示例1

输入

复制
8 14 6 8

输出

复制
3

说明

\hspace{15pt}在这个样例中,选 7 会导致按位或不符合条件,排除;剩下 {6, 8} 的所有非空子集都符合条件且按位与不同,因此输出 3
示例2

输入

复制
7 14 6 8

输出

复制
2

说明

\hspace{15pt}在这个样例中,选 8 按位与就会大于 n
示例3

输入

复制
10 14 1 8

输出

复制
5
示例4

输入

复制
114 5141 91 9810

输出

复制
8
示例5

输入

复制
1145 14191 9 810

输出

复制
219