D. 不同的序列

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

对于由小写字母构成的字符串 ,其有很多不同的非空子序列。

例如 ,其有子序列 等。

注意到 这一子序列出现了 次,但是我们认为这 个子序列是相同的,因此只计数一次。

请问 中有多少个不同的非空子序列,答案对 取模。

J-07-B

输入格式

输入一行,包含一个字符串 由小写字母构成

输出格式

输出一行,表示最终答案。

样例

样例输入1

aba

样例输出1

6

样例解释1

一共有 的子序列,其中 出现了 次,答案为 ​。

样例输入2

abaab

样例输出2

17

样例输入3,4

见下发文件。

样例输出3,4

见下发文件。

数据范围与提示

对于 的数据,

对于 的数据,

对于所有测评数据,