题目描述

一个边长为 $n$ 的三角形网格，是指将一个边长为 $n$ 的大等边三角形，用若干条平行于大三角形三条边的直线，划分成边长为 1 的小等边三角形。

我们把这些边长为 1 的小三角形的顶点称为网格的节点。

下图展示了边长为 4 的三角形网格。第一张图中画出了一个顶点均在网格节点上的等边三角形；第二张图中画出了两个顶点均在网格节点上的等边三角形。

题目要求

给定 $n,a,b$，求在边长为 $n$ 的三角形网格中，有多少个等边三角形满足：

• 三个顶点都在网格节点上；
• 边长在 $a$ 到 $b$ 之间，即边长 $L$ 满足：

答案对 $666013$ 取模。

输入格式

第一行包含三个整数 $n,a,b$，相邻整数之间用一个空格分隔。

输出格式

第一行输出一个整数，表示满足条件的等边三角形数量，对 $666013$ 取模。

数据范围与约定

• $1 \le n \le 1\,000\,000\,000$；
• $1 \le a \le b \le 1\,000\,000$。

样例

输入

4 1 2

输出

29

样例解释

在边长为 4 的三角形网格中：

• 有 16 个边长为 1 的小等边三角形，也就是覆盖整个网格的那些小三角形；
• 还有 6 个边长为 $\sqrt 3$ 的等边三角形，它们类似第二张图中的三角形，并且其中一条边竖直；
• 还有 7 个边长为 2 的等边三角形。

总数为：