PLEASE WRITE A C PROGRAM to Generate all palindromic decompositions of a string s (cut it into substrings that are palindromes). For example the string abbccd has 4 palindromic decompositions:

a, b, b, c, c, d,

a, b, b, cc, d,

a, bb, c, c, d,

a, bb, cc, d,

Requirements: In main (or another function that will be called in main), repeatedly read a string from the user, until the user enters -1.

For each of these strings, print the palindromic decomposition (one per line) and after that the total number of decompositions.

The function that generates the decompositions and counts them must be recursive.

The maximum string length is 100.

write the recurrence formula (T(n) = .... and the base case T(...) = ... ) for the recursive function that generates the palindromes as a function of the string length, N