Description

输入一个长度为n的数组{ai}(1 <= i <= n)

问有多少个长度为n的数组{xi}(1 <= i <= n)，满足1 <= xi <= ai。

并且相邻两项的最大公约数小于等于k。

换句话说，对于1<i <= n，满足gcd(xi−1,xi) <= k。

问这样的数组{xi}有多少个，答案对1000000007取模。

Format

Input

第一行两个整数n,k。

接下来一行n个整数，表示数组{ai}。

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

Output

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

Samples

9 2
1 2 3 4 5 6 7 8 9

168852