831. Print All K-Partitions of a String — Count (Mod 10^9+7)

Count ways to split string s into k non-empty consecutive parts = C(n-1,k-1) mod p. Input: 'k, "s"'.

Input: 'k, "s"'.

Output: Integer.

Examples

Example 1

Input: 2, "abc"
Output: 2
Explanation: C(2,1)=2.

Example 2

Input: 3, "abcd"
Output: 3
Explanation: C(3,2)=3.

Example 3

Input: 1, "hello"
Output: 1
Explanation: One way.