//mult(a,b) returns (a*b)%MOD
//add(a,b) returns (a+b)%MOD
//MOD=1000000009, C=115381398 or 276147934
int hsh(string s, int id)
{
	int ans=0;
	for(int i=0;i<s.length();i++)
	{
		ans=mult(ans,C);
		ans=add(ans,s[i]-'a'+1);
	}
	return ans;
}