题目背景

小依：你知道刀削面吗？

小铃：你不知道吗？！就是一只手拿着面团，另一只手里拿刀，站在开水锅前，把面团削成细长的薄片下进锅里煮的那种面！

小圈：你说得对，但是取模也是一种刀削面（？）

题目描述

给定长为 $n$ 的数列 $a$。对于一个非负整数 $x$，定义刀削面函数 $f(x) = x \bmod a _ 1 \bmod a _ 2 \bmod \cdots \bmod a _ n$（即先对 $a _ 1$ 取模，再对 $a _ 2$ 取模，一直取模到 $a _ n$）。

给出非负整数 $l, r$，求 $\sum \limits _ {i = l} ^ r f(i)$ 的值对 $10 ^ 9 + 7$ 取模的结果。

输入格式

第一行三个非负整数 $n, l, r$。

第二行 $n$ 个正整数表示 $a$ 数列。

输出格式

一行一个非负整数表示 $\sum \limits _ {i = l} ^ r f(i)$ 的值对 $10 ^ 9 + 7$ 取模的结果。

样例

样例输入 1

4 0 9
9 9 8 5 

样例输出 1

13

样例输入/输出 2

见下发文件 modulo2.in/ans。该样例满足测试点 $3 \sim 5$ 的限制。

样例输入/输出 3

见下发文件 modulo3.in/ans。该样例满足测试点 $8 \sim 11$ 的限制。

数据范围与提示

本题共 $20$ 个测试点，每个测试点 $5$ 分。

对于所有数据，$1 \le n \le 2\times 10 ^ 5$，$0 \le l \le r \le 10 ^ {18}$，$1 \le a _ i \le 10 ^ {18}$。

后记

小依 & 小铃：所以取模和刀削面到底有什么关系啊！

小圈：你们不知道吗？！就是一只手拿着原数，另一只手里拿模数，站在开水锅（？）前，把原数削成细长的模数下进锅里煮（？）的那种运算！