题目背景

时间定格在 2025 年 12 月 31 日的深夜，距离 2026 年元旦的钟声敲响只剩最后几分钟。

噜噜正坐在控制台前，负责向全宇宙发射“2026 新年问候信号”。往年的信号总是单调的“强度递增”，寓意步步高升。但经过这一年的思考，噜噜觉得单一的增长是不可持续的，真正的稳健在于 “动态平衡” ——就像物理学中的阻尼震荡，或者心电图的起伏，有升有降才是生命的律动。

“新的一年，我们要学会调节。” 噜噜对着麦克风自言自语，“不能一味索取，要在‘获得’与‘付出’之间寻找平衡。”

于是，它设计了一套全新的 “震荡信号协议”。在这个协议中，信号由若干个脉冲波段组成，每个波段的能量是 $2$ 的幂次，但带有极性：

• $+1$ 代表 “充能”（积累希望）；
• $-1$ 代表 “释放”（摒弃烦恼）；
• $0$ 代表 “静默”（养精蓄锐）。

为了维持信号的波形稳定，噜噜设定了核心规则：“充能与释放必须交替进行”。即：不可能连续两次“充能”中间没有“释放”，反之亦然。

现在，噜噜需要构建一条长度为 $N$ 的信号序列，使得这条信号的总能量值恰好落在“黄金区间” $\left[L,R\right]$ 内，以最完美的姿态迎接 2026 年的第一缕曙光。

题目描述

设一个长度为 $N$ 的序列 $A=\left[a_{N-1},a_{N-2},\dots ,a_{0}\right]$ 是一个合法的震荡信号，当且仅当它满足以下两个条件：

1. 极性约束：序列中的每一位 $a_{i}\in \left\{-1,0,1 \right\}$。
2. 交替约束：将序列中所有的 $0$ （静默）去除后，剩余的非零元素必须是正负交替的。
   • 例如： $\left[0,1,0,-1,1\right]$ 是合法的（非零子序列为 $1,-1,1$，正负交替）。
   • 例如： $\left[0,1,0,1\right]$ 是不合法的（非零子序列为 $1,1$，未交替）。
   • 特别地，全 $0$ 序列是合法的（视为静默状态，满足条件）。

该信号序列的总能量值 $Val\left(A\right)$ 定义为二进制加权和：

现在给定信号长度 $N$ 和目标能量区间 $\left[L,R\right]$。请你计算有多少种不同的合法震荡信号 $A$，使得其代表的总能量值满足：

由于方案数可能很多，请输出答案对 $10^{9}+7$ 取模后的结果。

输入格式

第一行一个整数 $T$，表示有 $T$ 组测试数据。

接下来共 $T$ 行，每行三个整数 $N,L,R$，分别表示信号长度、黄金区间的能量下界和上界。

输出格式

输出共 $T$ 行，每行一个整数，表示满足条件的合法震荡信号的方案数。

3
3 1 1
4 -2 2
60 -100 100

2
9
401

数据范围

对于 $20\%$ 的数据，满足 $N\le 12$，$-2^{12}\le L\le R\le 2^{12}$。

对于另 $30\%$ 的数据，满足 $N\le 60$，$0\le L\le R\le 10^{5}$。

对于 $100\%$ 的数据，满足 $1\le T\le 10$，$1\le N\le 60$， $-2^{60}<L\le R<2^{60}$。