题目描述

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

0

输入/输出例子2

EEDDCCBBAA
3

120

输入/输出例子3

RFEHSFDHFDHDSGFJNGFDSHFDHHSNDFHDSDGSDGXSDSHJDFJGFJFGDDKJGFDKJDGFFGDSBCDBCXVBNCXVNGFJGFJDGFJGFNFGGNGF
30

511931791