#include <stdio.h>
#include <string>
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
typedef long long int lld;
int C[29]; string str;
vector<lld> D;
const lld MOD = 1000000007;
int ci(char c) {
if ('a'<=c&&c<='z') return (int)((c-'a')+1);
return (int)((c-'A')+1);
}
int main() {
int t;cin>>t;
for (int ti=0; ti<t; ti++) {
cin>>str; memset(C,-1,sizeof(C));
lld res=1ll;
int len=str.length(); str="$"+str;
D=std::vector<lld>(len+2,0); D[0]=1ll;
for (int i=1; i<=len; i++) {
int cidx=ci(str[i]);
D[i]=D[i-1]*2ll;
if (C[cidx]!=-1) {D[i]-=D[C[cidx]-1];}
while (D[i]<0ll)
D[i]+=MOD;
D[i]%=MOD; C[cidx]=i;
}
if (ti) { printf("\n"); }
printf("%lld",D[len]);
}
return 0;
}
/*
I want to type this out 30 minutes ago, but I am disheartened to think
about the issue associated with +1.
I don't understand why people don't accept the time spent on questions,
or so-called stuck, failure, when it is the norm outside this office.
It is funny that people have the gut not to accept the world instead of
the world excluding them instead.
and this one is not at all intuitive and easy, although not as
difficult as contest problems just seen this morning. For those problems,
even if I have the solution code I still don't understand.
But this problem is different, it seems that I know what I don't know,
but can't know the exact problem, some feeling that can't be obtained
by copying others' solution, and can't be obtained from other activities as well.
What I do know now is the start must be an empty string.
the first character comes and there must have 2 possibilities.
nothing or character c.
If the next character is different, there are 4, and so on.
But if a character has existed before then obviously some subsequences are overlapped.
There is a way to resolve this, like cancelling out some prior existed strings.
if you keep track of some prior existed subsequences,
it is true that any possible subsequence exists.
The character may have appeared before,
So what that prior character can do can be done by the current one as well,
and so instead of -1, we actually need to - prior subsequence formed by the
prior char.
The code is so easy yet just can't tell the definite working way,
why it works, how it works, why must we count like this.
and to spend time on this is interesting.
*/ Write, Run & Share C++ code online using OneCompiler's C++ online compiler for free. It's one of the robust, feature-rich online compilers for C++ language, running on the latest version 17. Getting started with the OneCompiler's C++ compiler is simple and pretty fast. The editor shows sample boilerplate code when you choose language as C++ and start coding!
OneCompiler's C++ online compiler supports stdin and users can give inputs to programs using the STDIN textbox under the I/O tab. Following is a sample program which takes name as input and print your name with hello.
#include <iostream>
#include <string>
using namespace std;
int main()
{
string name;
cout << "Enter name:";
getline (cin, name);
cout << "Hello " << name;
return 0;
}
C++ is a widely used middle-level programming language.
When ever you want to perform a set of operations based on a condition If-Else is used.
if(conditional-expression) {
//code
}
else {
//code
}
You can also use if-else for nested Ifs and If-Else-If ladder when multiple conditions are to be performed on a single variable.
Switch is an alternative to If-Else-If ladder.
switch(conditional-expression){
case value1:
// code
break; // optional
case value2:
// code
break; // optional
......
default:
code to be executed when all the above cases are not matched;
}
For loop is used to iterate a set of statements based on a condition.
for(Initialization; Condition; Increment/decrement){
//code
}
While is also used to iterate a set of statements based on a condition. Usually while is preferred when number of iterations are not known in advance.
while (condition) {
// code
}
Do-while is also used to iterate a set of statements based on a condition. It is mostly used when you need to execute the statements atleast once.
do {
// code
} while (condition);
Function is a sub-routine which contains set of statements. Usually functions are written when multiple calls are required to same set of statements which increases re-usuability and modularity. Function gets run only when it is called.
return_type function_name(parameters);
function_name (parameters)
return_type function_name(parameters) {
// code
}