Count Splits into Substrings

You are given a non-empty string s and an integer k. Your task is to determine the number of ways to split the string s into exactly k non-empty substrings. A split is defined by choosing k - 1 distinct positions in the string (between characters) to break the string. In mathematical terms, if the length of s is n, then a valid split exists only if n \ge k, and the total number of ways to split the string is given by:

However, if n < k, then no valid splitting exists, and the answer is 0.

This problem requires you to implement an algorithm (possibly using dynamic programming) to compute the number of valid splits. The solution must read input from standard input and output the result to standard output.

inputFormat

The input is given via stdin and consists of two lines:

• The first line contains the string s.
• The second line contains the integer k.

You may assume that s contains only ASCII characters and that k is a non-negative integer.

outputFormat

Output a single integer (via stdout) representing the number of ways to split the string s into exactly k non-empty substrings.

abc
2

2