暂无测试数据。

等差数列是指从第二项起，每一项与它的前一项的差等于同一个常数的一种数列，这个常数叫做等差数列的公差，公差常用字母 $d$ 表示。比如 $7, 10, 13, 16$ 就是一个公差为 $3$ 的等差数列。

给定一个长度为 $n$，首项为 $a_0$，公差为 $d$ 的等差数列。

蒜头君想考考你，他觉得直接求出这个等差数列的和值太简单了，他想要你求从第一项开始每隔 $m$ 项选一项组成的新的数列的和值。

由于和值可能比较大，输出和值对 $1000000007$ 取模的结果。

输入格式

输入第一行三个整数 $n(1 \le n \le 10^{12})$, $a_0(0 \le a_0 \le 10^5)$, $d(0 \le d \le 10^5)$，分别表示等差数列的项数，首项和公差。

第二行输入一个整数 $m(0 \le m < n)$，表示每隔 $m$ 项选一个数。

输出格式

输出一行一个整数，表示新的数列所有项的和对 $1000000007$ 取模的结果。

样例解释

原始等差数列为 $2, 4, 6, 8, 10$，每隔 $1$ 项选一个，选出来的是 $2, 6, 10$。

5 2 2
1

18