We can solve this problem by finding the recurrence relation. Let A(n,m) be the number of ways in the string with length n for which exactly m characters come after theit neighbour to the left. We can call them ascents. We can construct such string either by placing a new character to string with length n - 1 and m - 1 ascents or placing a new character to the string n-1 with m ascents. In the first case we have string with m segments were characters are decreasing from left to right and we can put a new character in all n positions except for position 0 and and m-1 positions between ascending characters that is n-m positions. In the seconds case we have string with m+1 decreasing segment and we can put character at the begining of each segment that is we have m+1 choices. So A(n,m) = (n-m)*A(n-1,m-1) + (m+1)*A(n-1,m). A(n,0) = 1 for all n and A(n,n) = 0 for all n. The rest is trivial as we can use memoization to solve all test cases.