SP26913 SCELL - SUPER CELL

在天卫三，也就是天王星最大的卫星上，科学家们发现了一种被称为「超级细胞」的活细胞。它们认为这可能是该星球生命的起源。 这种超级细胞非常特别，每个细胞可以存活 **T** 秒。在每一秒钟，它会进行一次 **K-分裂**。在这个过程中，母细胞会产生 **K** 个新的超级细胞。这些新细胞同样可以存活 **T** 秒，并且它们在活着的时候也会继续进行 **K-分裂**。 超级细胞在第 0 秒被发现，并在接下来的 **T** 秒中生存，而到了第 **T** 秒便会死亡。因此，每个细胞自出生后的第 **T** 秒都会结束它的生命。 现在，你需要计算，在第 **N** 秒时，天卫三上有多少个超级细胞是活着的。

输入的第一行为一个整数 **TC**，表示测试用例的数量。随后有 **TC** 行，每行包含三个整数 **T**、**K** 和 **N**。**T** 是超级细胞的寿命（秒），**K** 是每次分裂所产生的新细胞数量，**N** 是你需要计算的时刻（秒）。

对于每个测试用例，输出在第 **N** 秒时活着的超级细胞数量，并对结果取模 $1000000007$（即 $10^9 + 7$）。

- $$1 \leq TC \leq 50$$ - $$0 \leq T \leq 30$$ - $$1 \leq K \leq 100$$ - $$0 \leq N \leq 1000000000$$ **样例：** **输入** ``` 3 5 2 4 3 1 5 1 2 4 ``` **输出** ``` 81 24 16 ``` **解释：** 第一个测试用例中： - 在第 0 秒，有 1 个细胞存在。 - 到第 1 秒，产生 2 个新细胞，总共 3 个存活。 - 到第 2 秒，产生 6 个新细胞，总共 9 个存活。 - 到第 3 秒，产生 18 个新细胞，总共 27 个存活。 - 到第 4 秒，产生 54 个新细胞，总共 81 个存活。 第二个测试用例中： - 在第 0 秒，有 1 个细胞存在。 - 到第 1 秒，产生 1 个新细胞，总共 2 个存活。 - 到第 2 秒，产生 2 个新细胞，总共 4 个存活。 - 到第 3 秒，产生 4 个新细胞，但第 0 秒时产生的细胞死亡，因此有 7 个存活。 第三个测试用例中： - 在第 0 秒，有 1 个细胞存在。 - 到第 1 秒，产生 2 个新细胞，但第 0 秒时产生的细胞死亡，因此有 2 个存活。 - 到第 2 秒，产生 4 个新细胞，但第 1 秒时产生的细胞死亡，因此有 4 个存活。 - 到第 3 秒，产生 8 个新细胞，但第 2 秒时产生的细胞死亡，因此有 8 个存活。 - 到第 4 秒，产生 16 个新细胞，但第 3 秒时产生的细胞死亡，因此有 16 个存活。 **本翻译由 AI 自动生成**