Preface:

All such solution are based on few simple rules:

```
( a + b ) mod m = ( a mod n + b mod n ) mod n
( a * b ) mod m = ( a mod n * b mod n ) mod n
```

With negative numbers there is a problem - http://ideone.com/LmWJva according to wikipedia this is 3, not -2, so before doing minus operation it is recommended to add n (which is removed after mod operation), `abs()`

is not working !!!

```
( a - b ) mod m = ( a mod n + n - b mod n ) mod n
```

What most of contestants are confused about is:

```
int MOD = 1000_000_007;
int a = 1000_000;
int b = 1000_000;
int c = ( a * b ) % MOD;
```

and while c is lower than MOD and a nad b are ints, it seems ok to use ints, but it is not…

Overflow occurs for `a * b`

command.

Example - http://ideone.com/OUBGvs notice the result is negative.

There are few tricks how to overcome this

- use
`1L * a * b`

- or to use bigger type, long in Java,
`long long`

in C/C++ not long !!!

Disadvantage of 1.) is, that you have to identify all places where you need to apply this. And also you one have to know very well what is he doing - see http://ideone.com/IuyPDt

It may seem like there is problem with multiply only and addition is ok, there is a catch also:

```
a + b = ( a + b ) mod M
```

the above is fine for a,b <= 10^{9} which it typical in problem statements…

But there is a problem if one tries to do

```
a + b + c = ( a + b + c ) mod M // there is overflow again - http://ideone.com/1glKK6
```

You may be interested also in this answer.

Few problems I searched quickly:

- LUCKY2
- TAPALIN

Note: see the 1000_000, this is valid 10^{6} in Java >= 7 and I love it, for more examples see SO, it is also possible to write binary numbers as `0b1011`

which is 11 in decimal…