骗你的，其实我是小红

题号：NC317839
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 给定一个区间 $[l,r]$ 和一个整数 $k$ ，其中 $k$ 是 $2$ 的非负整数次幂。
$\hspace{15pt}$ 请计算有多少个二元组 $i,j(l\leq i<j\leq r)$ ，满足 $i\operatorname{xor} j$ 是 $k$ 的倍数。

【名词解释】
$\hspace{15pt}$ $\operatorname{xor}$ ：指位运算中的按位异或（Bitwise XOR），对两个整数的二进制表示按位进行异或运算。如果您需要更多位运算相关的知识，可以参考 OI-Wiki的相关章节。

输入描述:

输入一行三个整数 。
保证  是  的非负整数次幂。

输出描述:

输出一行一个整数，表示满足条件的二元组数量。

示例1

输入

复制

1 6 4

输出

复制

说明

解释：满足条件的二元组为  和 ，它们的异或值均为 。