Alice 和 Bob 喜欢研究括号串。

称长度为 、仅由字符 与 构成的括号串 为合法，当且仅当：
对任意前缀，左括号数量不少于右括号数量；
整串中左括号与右括号各有 个。

对一个长度为 的合法括号串 ，定义 为 中等于字符串 的子序列的个数。换句话说， 等于满足 、且 、 的二元组 的数量。
对于给定整数 ，Alice 定义 。

但是，Bob 觉得 太简单，于是为同一个串 设计了另一种计数方式。设两个变量初值为 、。当 时依次重复以下过程：
令 为最大的正整数，使得第 个前缀中，左括号 的个数恰好等于 ；
更新 ；
更新 （注意执行顺序，要先更新 ）。
可以证明该过程一定能进行下去，并最终得到 ，且每一步都能保证 。
对于给定常数 ，Bob 定义 。

现在给出整数 ，对每个整数 ，设 为所有长度 的合法括号串集合，要求计算：


由于答案可能很大，你只需要输出 即可。

【名词解释】
字符串的前缀：从字符串的第一个字符开始，向后连续取若干个字符得到的字符串。更具体地，字符串 前 个字符构成的字符串被称为 的第 个前缀，也记为 。
子序列：从原序列中删除任意个（可以为零，也可以为全部）元素，且保持剩余元素相对顺序不变得到的新序列。

在一行上输入三个整数 。

在一行上输出  个整数，第  个整数表示  的值。

3 1 1

1 2 5

4 2 3

2 40 4544 2624512