Tangamandapio’s national competition is coming and it is time to write problems so all students are very excited to present their own problems. X likes subsequences and he wants to propose a problem about counting subsequences. Y loves permutations and he wants to propose a problem that requires knowing if a string has exactly K different permutations. Both of them think that their own problem is the best. Z is a friend of X and Y, and he wants to finish the discussion so he proposes to create a problem that combines both problems in one. Thus, they came with the following problem: Given a string of text S count the number of subsequence that have exactly K different permutations. A string T is a subsequence of another string S, if deleting some elements from S and without changing the order of the remaining elements, it is possible to get T. Input There are multiple test cases. Each Test case contains two lines. The first line is a string S (1 ≤ |S| ≤ 103) consisting of lowercase English alphabet. The second line contains an integer K (1 ≤ K ≤ 103). Output For each test case print exactly one line containing one integer representing the number of subsequences that have exactly K different permutations modulo 109 + 9. Sample Input aaab 3 abcc 2 Sample Output 3 5