#5472. 数列

内存限制:128 MiB 时间限制:10 Sec

题目描述

输入一个长度为n的数组{ai}(1 <= i <= n)
问有多少个长度为n的数组{xi}(1 <= i <= n),满足1 <= xi <= ai。
并且相邻两项的最大公约数小于等于k。
换句话说,对于1<i <= n,满足gcd(xi−1,xi) <= k。
问这样的数组{xi}有多少个,答案对1000000007取模。

输入格式

 第一行两个整数n,k。接下来一行n个整数,表示数组{ai}。

1 <= ai,k <= 1000000。Sigma(ai) <= 1000000。

输出格式

 一行一个整数表示这样的数组的个数,对1000000007取模。

样例

样例输入


			
9 2
1 2 3 4 5 6 7 8 9

样例输出


			
168852

数据范围与提示