题目背景

题目描述

对于所有长度为 $n$ 的仅包含 ‘0’、‘1’ 的 $2^n$种字符串，求满足以下条件的字符串数量：

• 至少包含一段长度不小于$a(a\leq n)$的连续的 ‘0’ 作为子串，或至少包含一段长度不小于 $b(b\leq n)$ 的连续的 ‘1’ 作 为子串。

由于满足条件的字符串可能有很多，只需要输出答案对 $10^9 + 7$ 取模的结果。

输入格式

本题有多组数据。第一行输入一个正整数 $T$，表示数据组数。对于每组数据：

一行输入三个正整数 $n,a,b$。

输出格式

每组数据输出 $T$ 行，第 $i$ 行一个整数表示答案对$10^9 + 7$取模的结果。

输入样例

2
10 3 2
114 51 4

输出样例

996
902195061

说明提示

对于 $10\%$ 的数据，$n\leq 10$。

对于 $20\%$ 的数据，$n\leq 100$。

对于 $50\%$ 的数据，$n \leq 1000$。

对于 $100\%$ 的数据，$1\leq T\leq 100,1\leq n\leq 10^5,1\leq a, b\leq n$。

本站补充：原套别：第 12 套 A 题。