ARC144D
题意略。
观察，发现 $x \& y + x |y = x+y$，原因是每个二进制位，如果出现两次，会计入二次，如果出现一次，会计入一次。猜想 $f(x)$ 的值与每个二进制位相关且对于每个二进制位独立。
考虑证明，对 $x$ 的二进制下 $1$ 的个数 $n$ 做归纳。
对于 $n=0$，$f(0)=f(0)$
对于 $n=1$，$f(2^i) = f(2^i)$
对于 $n=2$，$f(2^i+2^j) + f(0) = f(2^i) +f(2^j)$
考虑证明 $n=k$ 时， $f(x) +(k-1)f(0) = \sum\limits_{i\in x} f(2^i)$
设对于 $n=k-1$ 其成立，对于二进制位 1 个数为 k 的 x， $\forall i\in x,f(x)+f(0)=f(x-2^i) + f(2^i)$，易证 $f(x) +(k-1)f(0) = \sum\limits_{i\in x} f(2^i)$，且对于所有涉及元素二进制下 1 个数少于 n 的，所有限制满足。
故只需要确定 $f(2^i)$ 和 $f(0)$。其最终限制有两个，其一是，最大值不能超过 $k$，其二是最小值不能小于 0，最大值一定是把所有大于 $f(0)$ 的元素加起来，最小值则是把所有小于 $f(0)$ 的元素加起来。
枚举 $f(0)$ 和小于 $f(0)$ 的元素个数，我们可以将限制分配给对应元素 ，得到和式：
第一项计算那些小于 $f(0)$，第二项是将至多 $k$ 个冗余值分配给 $i$ 个小于 $f(0)$ 的元素的方案数，每个元素至少分配一个，或者说 $i$ 个正整数变量和为 $f(0)$ 的方案，可以给一个虚拟元素分别大于等于 0 个表示放弃，所以先给虚拟元素一个，变成 $f(0)+1$ 个元素插 $i$ 个板。最后一项是 $n-i$ 个非负整数变量，和不超过 $k-f(0)$ 的方案。先来个虚拟变量，然后先各自加 $1$，然后就是 $k-f(0)+n-i+1$ ，间隔是 $k-f(0)+n-i$ 个，版一共 $n$ 个。
解释完了，考虑计算，二维的，算不了。
考虑后两项的组合意义。
根据组合恒等式中的第五个。
对原式变形有
然后 $n$ 不大，维护个区间乘积枚举计算就行，记得对计算乘积的元素取模。
组合恒等式
题不是终点，组合恒等式才是重点
对上面那种图的组合恒等式，我们一一证明
式子1
组合意义证明
第一项是从 $r$ 个选 $m+k$ 个，第二项是从 $s$ 个选 $n-k$ 个，把两个拼在一起，从 $r+s$ 个中选 $n+m$ 个，容易发现和前者一一对应，故恒等。
代数证明
咕咕咕
式子2
组合意义证明
代数证明
咕咕咕