### 问题描述 给定 $a,b,n$，求 $$ \sum_{ i = 0}^{\left \lfloor \frac{n - b}{a} \right \rfloor} {\binom{n}{a \times i + b}} $$ 的值，由于结果可能很大，请输出结果对 $10^{9} +7$ 取模的值作为答案。 注： * 其中 $\lfloor x \rfloor$ 表示最大的不超过 $x$ 的整数，如 $\lfloor 1.2 \rfloor = 1,\lfloor 4 \rfloor =4$ 。 * 其中 $\dbinom{n}{m}$ 表示组合数，即 $\dbinom{n}{m} = C_n^m = \dfrac{n!}{(n-m)!m!}$ 。 ### 输入格式 第一行包含一个正整数 $T(1 \le T \le 3)$，表示测试用例的数量。 每个测试用例只有一行，包含三个正整数 $a, b, n(0 \le b < a \le 50, a \le n \le 10^{9})$。具体意义如题面所示。 ### 输出格式 对于每个测试用例，输出一行一个整数，表示答案。 ### 样例输入 ```text 3 1 0 10 20 2 1000 20 10 100000 ``` ### 样例输出 ```text 1024 208666789 572605725 ```