local function Pow(v, p, m) --возведение в степень по модулю
if p == 0 then return 1 end
if p == 1 then return v end
if p % 2 == 1 then return (Pow(v, p - 1, m) * v) % m end
local x = Pow(v, p / 2, m)
return (x * x) % m
end
for i = 1, 30 do
print(Pow(2, 1000000, 37))
end
bG9jYWwgZnVuY3Rpb24gUG93KHYsIHAsIG0pIC0t0LLQvtC30LLQtdC00LXQvdC40LUg0LIg0YHRgtC10L/QtdC90Ywg0L/QviDQvNC+0LTRg9C70Y4KICAgIGlmIHAgPT0gMCB0aGVuIHJldHVybiAxIGVuZAogICAgaWYgcCA9PSAxIHRoZW4gcmV0dXJuIHYgZW5kCgkKICAgIGlmIHAgJSAyID09IDEgdGhlbiByZXR1cm4gKFBvdyh2LCBwIC0gMSwgbSkgKiB2KSAlIG0gZW5kCiAgICAKICAgIGxvY2FsIHggPSBQb3codiwgcCAvIDIsIG0pCiAgICByZXR1cm4gKHggKiB4KSAlIG0KZW5kCgpmb3IgaSA9IDEsIDMwIGRvCiAgICBwcmludChQb3coMiwgMTAwMDAwMCwgMzcpKQplbmQ=