Due to technical reasons Codeforces may be unavailable on April 21st from 01:00-07:00 (MSK). ×

### anduturacila6's blog

By anduturacila6, history, 10 months ago, ,

Hello,

I was trying to solve Codeforces Round #489 (Div. 2), problem: (C) Nastya and a Wardrobe,(http://codeforces.com/contest/992/problem/C), and my solution so far gets the first 21 test cases right.

I know how to solve it, the only problem is outputting correctly using modulo.

My code currently looks like this:

import java.io.*;
import java.util.*;

public class Main {

public static int MOD = (int)Math.pow(10, 9)+7;

public static long powMod(long X,long N){
long result = 1;
X = X % MOD;
while(N > 0){
if(N % 2 == 1)
result = (result * X) % MOD;
N >>= 1;
X = (X*X)%MOD;
}
return result;
}

public static void main(String[] args) {
Scanner in = new Scanner(System.in);

long X = in.nextLong();
long K = in.nextLong();
if(X == 1)
System.out.println(powMod(2, K) + 1);
else if(X == 0)
System.out.println(0);
else if(K == 0)
System.out.println(X*2);
else {
long upperLimit = ((X%MOD) * powMod(2, K + 1));
long diff = (X - 1) % MOD;
long lowerLimit = (2*((-diff*((1-powMod(2, K)))) + (X%MOD)))%MOD;
if(X < 1000 && X > 100)
lowerLimit = (2*((-diff*((1-powMod(2, K)))) + (X%MOD)));

if(X > 1000 && K < 1000)
System.out.println((((upperLimit + lowerLimit)%MOD) / 2) % MOD);
else
System.out.println(((upperLimit + lowerLimit) / 2) % MOD);
}

}
}


I've tried several different combinations of modulo addition and multiplication, but none seem to reliably output the answer without me cheating a bit by adding if conditions.

I've seen the rules for modulo arithmetic and multiplication, but following those rules seems to get me even more qrong answers.

I was wondering what exactly am I doing wrong concerning the use of modulo and what to keep in my mind when I encounter similar problems.