公司名称

描述

有一家奶牛公司，它的名称是一个字符串 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

输出样例 1

0

**输入样例 2 **

EEDDCCBBAA 3

输出样例 2

120

**输入样例 3 **

RFEHSFDHFDHDSGFJNGFDSHFDHHSNDFHDSDGSDGXSDSHJDFJGFJFGDDKJGFDKJDGFFGDSBCDBCX VBNCXVNGFJGFJDGFJGFNFGGNGF

30

输出样例 3

511931791