You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

「UOI R2」写诗

题目背景

自从 happybob 和 JF 玩了飞花令之后，他一心想「提升语文素养」，于是，他决定练习写诗。

题目描述

他决定写一个长度为 $n$ 的诗。

不过我们都知道，诗是有平仄的要求的。同样，他写诗也有要求。

假设这个世界上有 $w$ 个字符（记作 $0\sim w-1$），对于诗里相邻两个字符 $a, b$，要求 $l\le \operatorname{popcount}(a\oplus b)\le r$，其中 $l, r$ 是给定的。

这里的 $\operatorname{popcount}$ 表示一个数在二进制下的表示中 $1$ 的个数。$\oplus$ 表示按位异或。

他想知道，在上述要求下，有多少种可能的诗？答案对 $1004535809$ 取模。

输入格式

一行，四个整数 $n, w, l, r$。

输出格式

一行，一个整数，表示答案。

样例 #1

样例输入 #1

3 4 1 2

样例输出 #1

36

样例 #2

样例输入 #2

10 17 2 3

样例输出 #2

756727588

样例 #3

样例输入 #3

66 129 3 6

样例输出 #3

820147337

样例 #4

样例输入 #4

542630838 1048576 7 13

样例输出 #4

289880585

提示

样例说明

对于样例 #1，由于 $\operatorname{popcount}(a\oplus b)\ne 0$，故 $a\ne b$，于是用容斥原理，有 $4^3-4^2-4^2+4=36$。

数据范围

本题采用捆绑测试。

记 $w=2^{lgw}+d(lgw=\lfloor\log_2{w}\rfloor>0)$，则：

对于 $100\%$ 的数据，$1\le n\le 10^9$，$0\le l\le r\le lgw \le 20$。