Subtask 1

For this subtask, we can brute force all the possible subsequences of ~N~ and check if they're equal to ~S~.

The only thing to be careful about is when ~S~ is a palindrome. This can only occur when ~|S| = 1~. Note that when ~S~ is a palindrome, then the strings found going left to right and right to left are identical, so we only need to check in one direction.

Time Complexity: ~O(2^N \times |S|)~.

Subtask 2

This solution demonstrates searching for valid solutions searching from left to right. Searching from right to left can be implemented similarly.

For the rest of this solution, let ~X[i]~ denote the ~i~th character of a string ~X~. Let the string of candies he lays on the ground be ~A~.

We can consider the fact that the ~S[i]~ will always appear after ~S[i-1]~ in ~A~

This means that if we create an integer array ~arr~ of size ~|S|~, we can store the number of subsequences in the string ~A~ equivalent to ~S~.

We do this by traversing backwards through the string ~A~. If ~A[i] = S[j]~ and ~S[j]~ is the last character of ~S~, then we add 1 to ~arr[j]~. If it is not the last character of ~S~, then we add ~arr[j+1]~ to ~arr[j]~, taking mod once added.

The answer is simply the first element of the array.

Our solution works by recording the total number of subsequences of ~S~ starting from the ~j~th character as the ~j~th element of the array, starting from the ~i~th character of ~A~. As we traverse the string ~A~ in reverse order, we're recording the number of subsequences of ~A~ equal to each substring of ~S~ that includes the last character, noting that any ~A[k]~ can be appended to the substring as long as ~k < i~, which is why we traverse through ~A~ backwards.

Time Complexity: ~O(N\times{|S|})~.