Distinct K-Character Subsequences

You are given a string s and an integer k. Your task is to count the number of distinct subsequences of s that have exactly k characters. A subsequence is obtained by deleting zero or more characters from s without changing the order of the remaining characters.

For example:

• If s = "abcde" and k = 3, then there are 10 distinct subsequences (all combinations of 3 characters from 5).
• If s = "aaaaaa" and k = 3, even though there are multiple ways to pick characters, all the subsequences are identical, so the answer is 1.

You must read the input from stdin and write the output to stdout.

inputFormat

The input consists of two lines:

1. The first line contains the string s.
2. The second line contains an integer k.

outputFormat

Output a single integer representing the count of distinct subsequences of s that have exactly k characters.

abcde
3

10