题目描述

津津、菲菲和皮皮在哈尔滨冰雪节上品尝了各种美食。他们发现，每种美食都有一个独特的"美味值"，所有"美味值"构成了一个整数数组$n$。现在，他们想要找出所有"美味组合"，即连续品尝的几种美食，其美味值的乘积小于一个特定的值$k$。请你来帮助他们计算这样的"美味组合"有多少个？

输入格式

输入分为三行：

• 第一行为$N$（$N$为已知成绩数量，$N \leq 30000$）
• 第二行为$K$
• 第三行$N$个整数，表示$N$个美味值

输出格式

返回子数组内所有元素的乘积严格小于$k$的连续子数组的数目。

样例

输入样例1

4
100
10 5 2 6

输出样例1

8

输入样例2

3
0
1 2 3

输出样例2

0

数据范围与提示

样例解释：8个乘积小于100的子数组分别为：$[10]$、$[5]$、$[2]$、$[6]$、$[10,5]$、$[5,2]$、$[2,6]$、$[5,2,6]$。需要注意的是$[10,5,2]$并不是乘积小于100的子数组。

数据范围：

• $1 \leq nums.length \leq 3 \times 10^4$
• $1 \leq nums[i] \leq 1000$
• $0 \leq k \leq 10^6$