题目描述

给定一个字符串 (s)，计算 (s) 中不同的非空子序列数量。

子序列是指从原字符串中删除若干个字符（也可以不删除），且不改变剩余字符相对顺序后得到的字符串。

由于答案可能很大，请输出答案对 $10^9+7$ 取模后的结果。

输入格式

输入一行一个字符串 (s)。

输出格式

输出一个整数，表示 (s) 中不同非空子序列的数量对 $10^9+7$取模后的结果。

输入输出样例

abc

7

aba

6

aaa

3

提示

对于样例 1，7 个不同的非空子序列分别为：

a、b、c、ab、ac、bc、abc。

对于样例 2，6 个不同的非空子序列分别为：

a、b、ab、ba、aa、aba。

对于样例 3，3 个不同的非空子序列分别为：

a、aa、aaa。

数据范围：

• $1 \le |s| \le 2000$
• $s$ 仅由小写英文字母组成