PROBLEM LINK:Author and Editorialist: Hussain Kara Fallah PREREQUISITES:NONE PROBLEM:Given a decimal integer $N$ (with no zeroes at all even as intermediate digits). Consider all left cyclic shifts of $N$. The left cyclic shift is the operation of removing the leftmost digit from the number and appending it to the end. Suppose $N = 123$ then all left cyclic shifts are {123,231,312}. So you start with $N$ and repeat the mentioned operation $N1$ times. Yalalovichik number of $N$ is equal to the concatenation of all these cyclic shifts. For the previous example: $Y = 123231312$. Given $N$, you need to compute the value of $Y$ modulo $10^9+7$ Length of $N$ may reach $10^5$ EXPLANATION:Let's assume that length of $N$ is equal to $L$. We know that: $N = a_0*10^{L1} + a_1*10^{L2} + a_2*10^{L3} + ... + a_{L1}$ Assuming that digits are indexed from $0$ to $L1$ and from left to right. $a_0$ represents the leftmost digit. So let's assume we need to do one shift operation, how to erase the leftmost digit? $N' = N  a_0*10^{L1}$ $N'$ is equal to the value of $N$ after removing the leftmost digit. Let's assume that the number resulting from the shift is $M$ so: $M = N' * 10 + a_0$ so now the number resulting from the shift is $M$ we need to append it to our final answer. At the beginning the answer $ans = N$. To append it let's shift $ans$ to the left by $L$ digits and simply add $M$. $ans = ans * 10^L + M$ This is for the first shifting operation, to solve the problem repeat this operation $N1$ times, but don't forget to continue working on the shifted number. We only need to calculate $10^L$ and $10^{L1}$, this can be done in linear time or faster if you prefer. To maintain the answer modulo $10^9+7$ we calculate the powers mentioned above modulo $10^9+7$ and we always take our results modulo $10^9+7$ after each subtraction or multiplication or addition. Refer to the implementations for more details. Total Complexity $O(L)$ AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 23 Dec '18, 23:10

Thanks, for this easy explanation . i am constantly getting TLE for this but now i can solve this answered 26 Dec '18, 19:56

i just want to know that is the constraint that N<=10^5 for integer or string of length 10^5 answered 26 Dec '18, 20:30

The link to my solution: https://github.com/executable16/CodeChef/blob/master/Yalalovivhik.cpp answered 29 Dec '18, 03:52

Can anybody help? Simple solution but doesn't work: https://ideone.com/nEqSN1 answered 04 Jan, 17:45

I was getting TLE as i was doing in O(L*L),now i can do it,good editorial. answered 20 Jan, 10:58

It could be rewritten $M = N * 10  a_0 * (10^L  1)$. So we only need to calculate $10^L$.
And we can do it while calculating $N$.