Recursive Substring Count

Background

Congcong is currently learning string processing. He encountered an interesting problem that requires determining if a substring appears a sufficient number of times within a longer string.

Problem Description

Given a string str and a non-empty substring sub, and a non-negative integer n. Recursively compute if sub appears at least n times somewhere in str, possibly with overlapping.

Input Format

The input consists of three lines.

The first line contains a string str. The second line contains a non-empty substring sub. The third line contains a non-negative integer n.

Output Format

Output a boolean value.

Output true if sub appears at least n times; otherwise, output false.

Sample

catcowcat
cat
2

true

Sample Explanation

In the string "catcowcat\