小雨的三角形
题号：NC26213
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述 

小雨手上有一个填满了数字的三角形。这个三角形一共有  层，其中第  层共有 个数，且第  个数和第  个数均为  。其余的数中，第  个数是上一层中第  个数和第  个数的和。小雨想知道这个三角形第  层到第  层所有数的和，一共有  个询问。

输入描述:

第一行两个正整数 ，表示这个三角形的层数和询问个数。

接下来  行，每行两个正整数 ，表示一次询问。

输出描述:

输出共  行，每行一个整数，表示一组询问的答案，对  取模。
示例1

输入

复制 
5 3
1 2
1 5
3 5

输出

复制 
5
83
78

说明

画出这个三角形：
1
2 2
3 4 3
4 7 7 4
5 11 14 11 5
第 1 \sim 2 层的和为  。

第 1 \sim 5 层的和为  。

第 3 \sim 5 层的和为  。

备注: