3041: 命运のRevue

时间限制:1000 ms 内存限制:128 MB
上传者:
提交:20 通过:2

题目描述

“$Starlight$,那是在星光指引下命运的故事。若你摘得小的星星,你能得到小的幸福,若你摘得大的星星,你将得到大的财富。若两者都能摘得,你将得到永远的愿望。摘星是罪孽的宽恕,摘星是夜晚的奇迹。抓住它吧!你所期望的那颗星。”
--------- 原来是$Hikari$酱陷入了命运のRevue

哇咖喱马斯。万恶的长颈鹿突然出现,挡住了恋哥哥救小光的必经之路!这下恋哥哥可头疼了,因为她的$non\ non$剑法正在$CD$中!更致命的是,不依不饶的长颈鹿给不擅长数学的恋哥哥出了个题,要求她计算出$\sum_{i=1}^{n}\dbinom{n}{i}x^{i}$。

长颈鹿$lpq$当然知道怎么做辣,现在他想考考你。
(注:$\dbinom{n}{i}$代表组合数$C(n,i)$。答案对$1e9+7$取模)


输入格式

输入第一行为一个整数$T(T \leq 60)$,表示一共有$T$组测试数据。

接下来有$T$行,每行有两个整数$x(1 \leq x \leq 10^5 ),n(1 \leq n \leq 10^9 )$。

输出格式

对于每组测试数据输出一个整数$y$,表示公式的答案。

输入样例 复制

2
2 1
3 2

输出样例 复制

2
15

数据范围与提示