Balanced Substring Partitioning

You are given a string S with length N and an integer K. Your task is to partition S into K contiguous non-empty substrings. The goal is to make the partition as balanced as possible by minimizing the difference between the length of the longest substring and the shortest substring.

In an optimal partition, the substrings will have lengths as equal as possible. In fact, if you let base = N // K and extra = N \mod K, then extra substrings will have length base + 1 and the remaining K - extra substrings will have length base. Therefore, the minimum difference between the longest and the shortest substring is:

[ \text{difference} = \begin{cases} 0, & \text{if } N \mod K = 0, \ 1, & \text{otherwise.} \end{cases} ]

Implement a program that computes this minimum difference.

inputFormat

The first line contains two integers N and K separated by a space.

The second line contains the string S consisting of N lowercase English letters.

outputFormat

Output a single integer: the minimum possible difference between the length of the longest and the shortest substring after partitioning.

## sample

7 3
abcdefg

1

</p>