时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
众所周知 Sumo 非常擅长数学题，今天他碰到了一道和 Fibonacci（斐波那契） 数列有关的题目。
Sumo 得到了一个长度为 n 的数组 a。
现在给出 q 次询问，每次询问给出一对正整数 l,r，将数组a中 [l,r] 区间的数
排序并去重后得到一个长度为m的数组 b。现在给出Fibonacci（斐波那契）数列的定义如下：
%5C%5C%0A%09%20%09%5Cend%7Bcases%7D)
Sumo 需要你来帮助他求出
对 
取模后的结果。
Sumo 得到了一个长度为 n 的数组 a。
现在给出 q 次询问，每次询问给出一对正整数 l,r，将数组a中 [l,r] 区间的数
Sumo 需要你来帮助他求出
输入描述:
第一行给出一个正整数，表示数组 a 的长度。
第二行给出 n 个正整数，第 i 个数表示。
第三行给出一个正整数，表示询问个数。
接下来 q 行每行一对正整数，表示询问的区间。
输出描述:
输出 q 行，第 i 行对应第 i 次询问给出的 l,r 的答案。
备注:
询问1中[1,3]区间排序去重后的结果为{1,2,3}，计算过程为:
1 * 1 + 2 * 1 + 3 * 2 = 9，
询问2中[1,4]区间排序去重后的结果为{1,2,3,4}，计算过程为:
1 * 1 + 2 * 1 + 3 * 2 + 4 * 3 = 21，
询问3中[2,5]区间排序去重后的结果为{2,3,4,5}，计算过程为:
2 * 1 + 3 * 1 + 4 * 2 + 5 * 3 = 28。