题目描述

给定一个正整数序列$\{a_i\}, i=1,2 \cdots N$，要求将其 划分 成恰好$K$个 非空 子段，每个子段内的元素之和$\le S$，求划分方案的总数。
“划分”指的是：序列中每一个元素都必须在某一个子段内，任意两个子段不能有交集。

I/O格式

输入

输入的第一行是一个正整数$T$，表示测试数据的组数。对于每组数据：
第一行是三个正整数$N, K, S$，第二行是$N$个正整数$a_1, a_2 \cdots a_N$。

输出

每组数据输出一行。分别表示该组数据的划分方案数对$10^5 + 3$取模后的结果。

样例

输入

2
4 2 10
6 2 3 5
5 3 10
3 3 6 4 3

输出

2
3

样例说明

第一组数据中划分方案有2种：$\{6\};\{2,3,5\}$和$\{6,2\};\{3,5\}$；
第二组数据中划分方案有3种：$\{3\};\{3,6\};\{4,3\}$，$\{3,3\};\{6\};\{4,3\}$和$\{3,3\};\{6,4\};\{3\}$。

数据规模及约定

20%的数据：$T \le 50, \quad N \le 15, \quad K = 4$
另外20%的数据：$T \le 20, \quad N \le 15, \quad K \le 6$
另外30%的数据：$T \le 10, \quad N \le 150, \quad K \le 10$
另外30%的数据：$T \le 10, \quad N \le 1.5 \times 10^4, \quad K \le 10$
所有数据均满足：$S \le 10^8,\quad \displaystyle\sum_{i=1}^{N} a_i \le K \times S$
时间限制1s，空间限制256MB。