## PROBLEM LINK:

**Author:**

deadwing97

**Editorialist (Unofficial):**

Abhishek Mohanty

## DIFFICULTY:

Easy

## PREREQUISITES:

Modular Arithmetic

## PROBLEM:

Given N.

Compute all its distinct left shifts and append them together in the same order. Finally find the mod of the resulting number wrt 1000000007

For example, if N=123, the left shifts are 123,231,312 and thus Y_N = 123231312.

output = Y_N % (10^9+7) = 123231312

## EXPLANATION:

**Constraints**

Here the *number of digits* in N can go upto 10^5

**i.e. N** < \bf{10^{10^5}}

**Result**

Let

m = 10^9 + 7

a = no.\ of\ digits\ in\ N\ (this\ can\ go\ upto\ 10^5\ )

then

123231312 \% m = ((123 * 10^6)\%m + (231 * 10^3)\%m + (312 * 10^0)\%m) \%m

Thus the above output can be written in terms of the modulus of the individual left shifts as follows

Y_N = (\ \displaystyle\sum_{i=0}^{a - 1} 10^{ia} * N_{a - 1 - i}\ )\ \% m

If we can compute all the left shifts i.e N_i\ \forall i in \mathcal{O}(1) we can solve the problem

**Computing left shifts**

We will compute all the prefixes and suffixes modulus wrt m.

For N\ =\ 12345,\ a = 5

Prefixes modulus would be

```
P[0] = 0 (for the full string)
P[1] = 1 % m
P[2] = 12 % m
P[3] = 123 % m
P[4] = 1234 % m
P[5] = 12345 % m
```

Suffixes modulus would be

```
S[1] = 5 % m
S[2] = 45 % m
S[3] = 345 % m
S[4] = 2345 % m
S[5] = 12345 % m
```

All the left shifts can now be computed as

N_i\ =\ (S[a - i] * 10^i + P[i])\ \% m

**Complexity:**

We first compute the prefixes and suffixes modulus with \mathcal{O}(a)

We then compute all the left shifts with \mathcal{O}(a)

We then compute Y_N where the computing 10^{ia} will cost \mathcal{O}(log a) and the loops will cost \mathcal{O}(a)

Thus complexity of algorithm is \mathcal{O}(aloga)

where a = \mid N\mid = 10^5

## EDITORIALISTâ€™S SOLUTION:

**PS :** *Its my first ever post on codechef, please bear with me if I violated any standards *

*Happy Coding*