题目描述

给定一个正整数序列\(\{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。