# MMSCORE -Editorial

Tester: Ram Agrawal
Editorialist: Prathamesh Sogale

EASY-MEDIUM

# PREREQUISITES:

Greedy, DP, Math etc. Ideally with the links to Wikipedia

# PROBLEM:

Yesterday, Meena appeared in a quiz competition, where he answered N questions correctly. There were a total of Q questions in the quiz. The result of the quiz has not been declared yet. Meena is too eager to know his score. He wants to find his score by today. The rules of the quiz were as follows:

• The judges use a counter to note any participant’s score, there is a separate counter for every participant. The counter is used to note the consecutive correct answers.
• If a participant answers a question incorrectly, then the counter is reduced to 0.
• If a participant’s counter reaches a value dd, then the counter is reset and the participant’s score gets doubled.

Now, the problem with Meena is, he doesn’t remember in what order he answered the questions. Help Meena find out his possible minimum score.

If the answer is too big, output it modulo 10^9+7.

# EXPLANATION:

Let w=Q-N representing number of wrong answers.

If (w+1)*(d-1) \geq n, in this case he doesn’t answer continuously more than d-1 questions correctly. So the his score equals N.

Now,

To find the minimum score, lets consider the order of correct answers is like

He answers d-1 questions correctly then a wrong answer then again d-1 questions correctly and so on untill the wrong answer count equals w and then he answers all the remaining question correct continuously.

con=N-w*(d-1) .
Assign: p=2,ans=1

The number of times his score gets doubled can be given by:
t=con/d.
Find the answer by running a while loop till t!=0.
In the loop check if t is odd then ans=ans*p. reduce t by a factor of 2, that is t=t/2. p=p*p%mod

After the loop
ans=(ans-1)*2*d+n-t*d

# SOLUTIONS:

Setter's Solution
``````from sys import stdin
mod=10**9+7
q, n, d = map(int, stdin.readline().strip().split())
if((w+1)*(d-1)>=n):
print(n)
continue
con=n-w*(d-1)
t=con//d
ans=1
p=2
t2=t
while(t2!=0):
if(t2&1):
ans*=p
ans=ans%mod
t2//=2
p=p*p%mod
ans=((ans-1)*2*d+n-t*d)%mod
print(ans)
``````