C. 羊圈魔法

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

在遥远的「幻影羊圈」中，守护着 $n$ 块魔法符文。这些符文拥有神奇的力量，只有当你采集到某一区间数量的符文，才能合成灵药，助力勇者闯关。传说主人公“噜噜”与他的小伙伴“一只羊”一同深入羊圈，需要不断地采集和组合符文，才能完成一系列炼药任务。

给定符文总数 $n$ 和任务数 $q$ ，第 $i$ 个任务指定一个区间 $[l_i, r_i]$ ，需要计算选取符文数量在该区间内的所有方案数之和：

\sum_{k=l_i}^{r_i} \binom{n}{k}

请对每个任务输出该值对 $10^9+7$ 取模的结果。

第一行包含两个整数 $n$ 和 $q$ ，分别表示符文总数和任务数。接下来 $q$ 行，第 $i$ 行包含两个整数 $l_i$ 和 $r_i$ ，表示第 $i$ 个任务的查询区间。

共 $q$ 行，第 $i$ 行输出第 $i$ 个任务对应的答案，即

\sum_{k=l_i}^{r_i} \binom{n}{k} \bmod (10^9+7).

16
25
26

子任务编号	$n$	$q$	分值占比
$1$	$\le10$		$10\%$
$2$	$\le10 ^ 3$	$\le10^3$	$15\%$
$3$	$\le10 ^ 5$		$25\%$
$4$	$\le10 ^ 6$		$20\%$
$5$	$\le10 ^ 6$	$\le10^5$	$30\%$