Jersey Number

All submissions for this problem are available.
It’s World cup time, and every player wants to get a cool jersey number. As a result, there was a fight between the players about what jersey number they can have. To resolve this, the committee (ICC) came up with an idea.
They gave a huge string and asked each player to walk in one by one, and select four indices in the string (i, j, k, l) such that i<=j and k<=l and the substrings S[i..j], S[k..l] should have a nonempty substring in common. Also, (i, j, k, l) should not have been chosen by any player who walked in earlier. If the player is able to give a correct answer (i, j, k, l), he gets "ijkl" as his jersey number.
Assuming that there are enough players to claim all valid jersey numbers, and that all players are equally smart (i.e if there is any valid (i, j, k, l), then they’ll give the right answer), find the number of distinct jersey numbers that can be assigned.
Note: The huge string chosen by the ICC is hexadecimal. (Only contains ‘0’‘9’ and uppercase characters ‘A’‘F’).
Input:
The first line of input contains a single integer ’T’, denoting the no. of test cases.
Each of the following ’T’ lines contains a sting S, chosen by the ICC.
Output:
Print one line for each test case, denoting the answer modulo 1000000007.
Constraints:
1 <= T <= 200
1 <= S <= 100000
1 <= Sum of S over all test cases <= 1000000
S is hexadecimal. (Only contains ‘0’‘9’ and uppercase characters ‘A’‘F’)
Sample Input:
3
AB
ACC
A2011
Sample Output:
7
30
163
Explanation:
For the case "AB", following are valid jersey numbers:
{“1111”, “1112”, “1211”, “1212”, “1222”, “2212”, “2222”}
Author:  murdocc007 
Editorial  http://discuss.codechef.com/problems/AMR14F 
Tags  amr14ros, hard, murdocc007 
Date Added:  27122014 
Time Limit:  4 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 