Hackerearth QAS

                   Baba & Guruji

Baba wants to kill Guruji. He has a master plan but Guruji is prepared for him.

Baba released a bacterial concentration of 1 unit in Guruji's underground water source on Day 0. The concentration of bacteria becomes xtimes the concentration day before. But,Guruji's powder kills y units of bacteria each day, starting from Day 1.

Guruji needs your help to estimate the concentration of bacteria on the N th day.

Note : Large Input/Output Data. Use fast I/O.

Input :

First line consists of 2 space separated integers x and y. The next line consists of a single integer Q, denoting the number of queries Guruji has for you. The next Q lines are such that each line consists of a single integer N.

Output :

For each query of Guruji, print the number of bacteria present on the N th day on a new line. Since the answer can be really huge, print the answer modulo 1000000007 (10^9 + 7) .

Constraints :

2<=x<=100

0<=y<=(x-2)

1<=Q<=10^6

1<=N<=10^6

1. #include<iostream>
2. #include<cstdio>
3. #include<string>
4. #define ull long long int
5. using namespace std;
6. #define max 1000001
7. #define mod 1000000007
8. ull conc[max];
9. void pre(int x,int y)
10. {
11.  conc[0]=1;
12.  for(int i=1;i<max;i++)
13.     {
14.       conc[i]=(conc[i-1]*x)%mod-y;
15.     }
16. }
17. int main()
18. {
19.     int x,y;
20.     int Q,N;
21.     scanf("%d",&x);
22.     scanf("%d",&y);
23.     scanf("%d",&Q);
24.     pre(x,y);
25.     for(int j=0;j<Q;j++)
26.     {
27.      scanf("%d",&N);
28.      printf("%d\n",conc[N]%mod);
29.     }
30. }