题目描述

有一颗无限大的树，每个节点有 \(n\) 个子节点，连接它与第 \(i\) 个子节点的边长为 \(a_i\)。求这颗树上有多少节点与根节点的距离小于等于 \(k\)。对 \(1e9+7\) 取模

输入格式

第一行两个数 \(n\),\(k\)

第二行 \(n\) 个数，第 \(i\) 个数代表 \(a_i\)

输出格式

这棵树上离根节点距离小于等于 \(k\) 的节点个数

样例

样例输入 1

2 4
1 2

样例输出 1

7

提示说明

对于 30% 的数据

\( n \le 10 \)

对于 60% 的数据

\( k \le 10^3 \)

对于 100% 的数据

\( n \le 10^5 \)

\( k \le 10^9 \)

\(a_i \le 100\)