题目描述
有一家奶牛公司，它的名称是一个字符串S。该公司最近发现一个问题，客户很难在互联网
搜索到该奶牛公司，因为互联网搜索显示的结果是按照公司名称的字典序从小到大排序显示
的。因为奶牛公司名称的字典序比较靠后，所以很难显示给新客户看。于是奶牛公司想更改
公司名称。但奶牛公司又不想对公司名称改动太大，因为害怕老客户抵触。
奶牛公司决定这样操作：
1、选中S 的恰好k 个下标，不妨设为d1,d2,...dk，且0 <= d1 < d2 < d3 <... < dk < S.size()。
2、你可以对S 的这k 个位置的字符任意交换位置。
3、S 其它位置不变。
经过上述操作后，必须使得公司名称的字典序比原来的字典序小，这样就更容易被新客户搜
索到。问题是：有多少种不同的集合{d1,d2,d3,....dk}满足条件？答案模1000000007。
输入
第一行，一个字符串S，长度不超过2000，全部是右大写英文字母构成。
第二行，一个正整数K， 1 <= K <= S.size()。
输出
一个整数
样例输入输出
输入#1
复制
ABCDE
2
【输入样例2】
EEDDCCBBAA
3
【输入样例3】
RFEHSFDHFDHDSGFJNGFDSHFDHHSNDFHDSDGSDGXSDSHJDFJGFJFGDDKJGFDKJDGFFGDSBCDBCX
VBNCXVNGFJGFJDGFJGFNFGGNGF
30
提示