Blice 和阿强巴是好朋友。
但萌萌哒 Blice 不擅长数学，所以阿强巴给了她一些奶牛做联系。
阿强巴有 头奶牛，他需要把这些奶牛划分成若干组，每组种至少有一头奶牛，当 时，方案 和 是相同的方案，而方案 和 则是不同的方案。
现在阿强巴想直到有多少种不同的划分方案……不不不，这对于 Blice 时在太简单了，所以阿强巴要出的再难一点。
因此阿强巴又定义了一个二元函数 ，设一个划分方案数列 ，长度为 （下标从 开始），那么对于该划分方案来说，它的价值就是 ，显然当 时，这个划分方案的价值为 。
（ 的具体含义会在后面给出）
现在阿强巴想直到所有不同的划分方案的价值总和……不不不，这对于 Blice 时在太简单了，所以阿强巴要出的再难一点。
因此阿强巴又生成了一个数列 ，长度为 （下标从 开始），他重新定义了划分方案的价值，即 ，这里的 是数列下标。
Blice 终于不会做了，你能帮帮她吗？
由于答案可能很大，你只需要数处模 意义下的答案。
