Hello all,I was doing a hiring challenge on hackerearth and got really stuck in this problem and couldn't solve it yet.

You are given a string of length N consisting of only lowercase alphabets and two alphabets x and y. There are Q queries given and each query will be specified by two integers l and r. You have to consider the sub string [l,r] of the given string and count the total number of distinct sub sequences of the sub string which starts with x and ends with y modulo 1e9+7. 1<=N<=1e5 1<=Q<=1e5 0<=l<=r<=N-1. Example: Input: 4 aabb a b 4 0 2 1 3 2 3 0 3 Output: 3 3 0 9

Any help is appreciated. Thanks in advance.