Problem Description

A subsequence is obtained from a string by deleting zero or more characters without changing the order of remaining elements. The original string qualifies as its own subsequence.

For a given lowercase string s of length n (1 ≤ n ≤ 1000), count how many subsequences contain exactly k ditsinct letter types (1 ≤ k ≤ 26). Return the answer modulo 10^9 + 7.

Input:

• First line: n and k
• Second line: string s

Output:

• Single integer result

Example:

6 5
eecbad

Output: 3

The string eecbad has 5 distinct letters. Valid subsequences include the full string and two ecbad variants (by removing one 'e').

Solution Method

The solution combinse frequency analysis with dynamic programming.

For each character appearing c times, there are 2^c - 1 ways to select a non-empty subset of its occurrences. Precompute this for all 26 letters.

Let choices store these values for letters that actually appear in s. The problem reduces to picking exactly k elements from choices and multiplying them, summing all possible combinations.

Dynamic programming efficiently computes this sum:

• dp[j] = total count for j distinct letters
• Initialize dp[0] = 1
• Process each value v in choices:
  • For j from k down to 1:
    • dp[j] = (dp[j] + dp[j-1] * v) % MOD
• The answer is dp[k]

Backward iteration prevents reuse of the same letter in one subsequence.

Code

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1000000007;

long long mod_pow(long long base, long long exp) {
    long long result = 1;
    while (exp > 0) {
        if (exp & 1) result = (result * base) % MOD;
        base = (base * base) % MOD;
        exp >>= 1;
    }
    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, k;
    if (!(cin >> n >> k)) return 0;
    
    string s;
    cin >> s;
    
    vector<int> freq(26, 0);
    for (char ch : s) freq[ch - 'a']++;
    
    vector<long long> letterChoices;
    for (int i = 0; i < 26; ++i) {
        if (freq[i] > 0) {
            long long ways = (mod_pow(2, freq[i]) - 1 + MOD) % MOD;
            letterChoices.push_back(ways);
        }
    }
    
    if (k > (int)letterChoices.size()) {
        cout << 0 << '\n';
        return 0;
    }
    
    vector<long long> dp(k + 1, 0);
    dp[0] = 1;
    
    for (long long choice : letterChoices) {
        for (int j = k; j >= 1; --j) {
            dp[j] = (dp[j] + dp[j-1] * choice) % MOD;
        }
    }
    
    cout << dp[k] << '\n';
    return 0;
}