Palindromic Subsequence

Given a string s and an integer k, determine whether there exists a palindromic subsequence of exactly length \( k \) in s. A subsequence is a sequence derived from the string by deleting some or no elements without changing the order of the remaining characters. Note that if the longest palindromic subsequence (LPS) of s has length \( L \) and \( L \ge k \), then it is always possible to obtain a palindromic subsequence of length exactly \( k \) by removing appropriate characters from that LPS.

Input Format: The input consists of two lines. The first line contains the string s and the second line contains the integer k.

Examples:

• Input: abcbab and 3 → Output: True
• Input: abcdef and 2 → Output: False

inputFormat

The input is read from standard input and contains two lines:

1. The first line is a string s composed of lowercase letters.
2. The second line is an integer k representing the required length of the palindromic subsequence.

outputFormat

Output a single line to standard output: True if there exists a palindromic subsequence of length exactly k in s, otherwise output False.

## sample

abcbab
3

True

</p>