暂无测试数据。

等比数列是指从第二项起，每一项与它的前一项的比值等于同一个常数的一种数列，这个常数叫做等比数列的公比，公比常用字母 $q$ 表示。比如 $2, 4, 8, 16$ 就是一个公比为 $2$ 的等比数列。

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

蒜头君想考考你，他觉得直接求出这个等比数列的和值太简单了，他想要你求从第一项开始每隔 $m$ 项选一项组成的新的数列的和值。由于结果可能会很大，输出和值对 $1000000007$ 取模的结果。

输入格式

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

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

输出格式

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

样例解释

原等比数列为 $2, 4, 8, 16, 32$，每隔 $1$ 项选一个数，新的数列为 $2, 8, 32$。

5 2 2
1

42