Use the frequency array of characters of the string.
For 1 ≤ m ≤ s.length, count the number of subsequences of s where each character occurs exactly m times.
For any n and k, you can calculate (n choose k) mod p in O(log p) using binary exponentiation.