Por Costel the pig, our programmer in-training, has recently returned from the Petrozaporksk training camp. There, he learned a lot of things: how to boil a cob, how to scratch his belly using his keyboard, etc... He almost remembers a programming problem too:

A semipalindrome is a word  for which there exists a subword  such that  is a prefix of  and  (reverse ) is a suffix of . For example, 'ababba' is a semipalindrom because the subword 'ab' is prefix of 'ababba' and 'ba' is suffix of 'ababba'.

Let's consider only semipalindromes that contain letters 'a' and 'b'. You have to find the -th lexicographical semipalindrome of length .

Por Costel doesn't remember if the statement was exactly like this at Petrozaporksk, but he finds this problem interesting enough and needs your help to solve it.

#include<cstdio>

using namespace std;

#define MOD 10000003

typedef long long ll;

int n,a,b,x1,q,q1;

int anss[100010];

int main()

{

	freopen("pocnitoare.in","r",stdin);

	freopen("pocnitoare.out","w",stdout);

//	freopen("k.in","r",stdin);

	scanf("%d%d%d%d%d%d",&n,&a,&b,&x1,&q,&q1);

	int now=x1;

	anss[1]=now;

	for(int i=2;i<=10000003;++i)

	  {

	  	now=(int)((((ll)now*(ll)(i-1)%(ll)n)%(ll)n+(ll)a%(ll)n)%(ll)n);

	  	if(i%100==1)

	  	  anss[i/100+1]=now;

	  }

//	int now=anss[q1/100+1];

//	int tmp=q1%100-1;

//	for(int i=1;i<=tmp;++i)

//	  now=(int)((((ll)now*(ll)(i-1)%(ll)n)%(ll)n+(ll)a%(ll)n)%(ll)n);

//	printf("%d\n",now);

	for(int i=1;i<=q;++i)

	  {

	  	if(i!=1)

	  	  q1=((int)((ll)(i-1)*(ll)now%(ll)MOD)+b%MOD)%MOD+1;

	  	now=anss[(q1-1)/100+1];

		for(int j=(q1-1)/100*100+2;j<=q1;++j)

	  	  now=(int)((((ll)now*(ll)(j-1)%(ll)n)%(ll)n+(ll)a%(ll)n)%(ll)n);

		printf("%d\n",now);

	  }

	return 0;

}