/+ dub.sdl: name "A" dependency "dcomp" version=">=0.6.0" +/ import std.stdio, std.range, std.conv, std.algorithm; // import dcomp.scanner; // import dcomp.modint; alias Mint = ModInt!(10^^9 + 7); long[] len; long lenInit(int k) { len = new long[](k+1); long ba = 1; len[1] = 1; foreach (long i; 2..k+1) { ba = 2*ba + (i*i).to!string.length; len[i] = ba; } return ba; } long calcSumNaive(long l, long r, string s) { l = max(l, 0L); r = min(r, s.length); long sm = 0; foreach (long i, c; s) { int u = c - '0'; if (u == 0) u = 10; if (l <= i && i < r) { sm += u; } } return sm; } long[] sumDP; bool[] sumUsed; static this() { sumDP = new long[100]; sumUsed = new bool[100]; } long calcSum(long l, long r, int k) { l = max(l, 0L); r = min(r, len[k]); if (r <= l) return 0; bool full = (l == 0 && r == len[k]); if (full && sumUsed[k]) return sumDP[k]; if (full) sumUsed[k] = true; long ans = 0; ans += calcSum(l, r, k-1); long di = len[k-1]; string s = (k*k).to!string; ans += calcSumNaive(l-di, r-di, s); di += s.length; ans += calcSum(l-di, r-di, k-1); if (full) sumDP[k] = ans; return ans; } Mint calcMulNaive(long l, long r, string s) { l = max(l, 0L); r = min(r, s.length); Mint sm = 1; foreach (long i, c; s) { int u = c - '0'; if (u == 0) u = 10; if (l <= i && i < r) { sm *= Mint(u); } } return sm; } Mint[] mulDP; bool[] mulUsed; static this() { mulDP = new Mint[100]; mulUsed = new bool[100]; } Mint calcMul(long l, long r, int k) { l = max(l, 0L); r = min(r, len[k]); if (r <= l) return Mint(1); bool full = (l == 0 && r == len[k]); if (full && mulUsed[k]) return mulDP[k]; if (full) mulUsed[k] = true; Mint ans = 1; ans *= calcMul(l, r, k-1); long di = len[k-1]; string s = (k*k).to!string; ans *= calcMulNaive(l-di, r-di, s); di += s.length; ans *= calcMul(l-di, r-di, k-1); if (full) mulDP[k] = ans; return ans; } int main() { auto sc = new Scanner(stdin); int k; long l, r; sc.read(k, l, r); l--; k = min(k, 60); lenInit(k); if (len[k] < r) { writeln("-1"); return 0; } auto sm = calcSum(l, r, k); auto ml = calcMul(l, r, k); writeln(sm, " ", ml); return 0; } /* IMPORT /home/yosupo/Program/dcomp/source/dcomp/modint.d */ // module dcomp.modint; // import dcomp.numeric.primitive; struct ModInt(uint MD) if (MD < int.max) { import std.conv : to; uint v; this(int v) {this(long(v));} this(long v) {this.v = (v%MD+MD)%MD;} static auto normS(uint x) {return (x a[n-1]*T(n)).take(length).array; } // optimize T[] invFactTable(T)(size_t length) if (isModInt!T) { import std.algorithm : map, reduce; import std.range : take, recurrence, iota; import std.array : array; auto res = new T[length]; res[$-1] = T(1) / iota(1, length).map!T.reduce!"a*b"; foreach_reverse (i, v; res[0..$-1]) { res[i] = res[i+1] * T(i+1); } return res; } T[] invTable(T)(size_t length) if (isModInt!T) { auto f = factTable!T(length); auto invf = invFactTable!T(length); auto res = new T[length]; foreach (i; 1..length) { res[i] = invf[i] * f[i-1]; } return res; } unittest { import std.stdio; alias Mint = ModInt!(10^^9 + 7); auto r = factTable!Mint(20); Mint a = 1; assert(r[0] == Mint(1)); foreach (i; 1..20) { a *= Mint(i); assert(r[i] == a); } auto p = invFactTable!Mint(20); foreach (i; 1..20) { assert((r[i]*p[i]).v == 1); } } /* IMPORT /home/yosupo/Program/dcomp/source/dcomp/scanner.d */ // module dcomp.scanner; class Scanner { import std.stdio : File; import std.conv : to; import std.range : front, popFront, array, ElementType; import std.array : split; import std.traits : isSomeChar, isStaticArray, isArray; import std.algorithm : map; File f; this(File f) { this.f = f; } string[] buf; private bool succ() { while (!buf.length) { if (f.eof) return false; buf = f.readln.split; } return true; } private bool readSingle(T)(ref T x) { if (!succ()) return false; static if (isArray!T) { alias E = ElementType!T; static if (isSomeChar!E) { //string or char[10] etc x = buf.front; buf.popFront; } else { static if (isStaticArray!T) { //static assert(buf.length == T.length); } x = buf.map!(to!E).array; buf.length = 0; } } else { x = buf.front.to!T; buf.popFront; } return true; } int read(T, Args...)(ref T x, auto ref Args args) { if (!readSingle(x)) return 0; static if (args.length == 0) { return 1; } else { return 1 + read(args); } } } unittest { import std.path : buildPath; import std.file : tempDir; import std.algorithm : equal; import std.stdio : File; string fileName = buildPath(tempDir, "kyuridenanmaida.txt"); auto fout = File(fileName, "w"); fout.writeln("1 2 3"); fout.writeln("ab cde"); fout.writeln("1.0 1.0 2.0"); fout.close; Scanner sc = new Scanner(File(fileName, "r")); int a; int[2] b; char[2] c; string d; double e; double[] f; sc.read(a, b, c, d, e, f); assert(a == 1); assert(equal(b[], [2, 3])); assert(equal(c[], "ab")); assert(equal(d, "cde")); assert(e == 1.0); assert(equal(f, [1.0, 2.0])); } /* IMPORT /home/yosupo/Program/dcomp/source/dcomp/numeric/primitive.d */ // module dcomp.numeric.primitive; import std.traits; T pow(T, U)(T x, U n) if (!isFloatingPoint!T && isIntegral!U) { return pow(x, n, T(1)); } T pow(T, U)(T x, U n, T e) if (isIntegral!U) { while (n) { if (n & 1) e *= x; x *= x; n /= 2; } return e; } unittest { assert(pow(3, 5) == 243); assert(pow(3, 5, 2) == 486); } T lcm(T)(in T a, in T b) { import std.numeric : gcd; return a / gcd(a,b) * b; } unittest { assert(lcm(2, 4) == 4); assert(lcm(3, 5) == 15); assert(lcm(1, 1) == 1); assert(lcm(0, 100) == 0); } //a*T[0]+b*T[1]=T[2], T[2]=gcd //todo: to binary extgcd T[3] extGcd(T)(in T a, in T b) if (!isIntegral!T || isSigned!T) //unsignedはNG { if (b==0) { return [1, 0, a]; } else { auto e = extGcd(b, a%b); return [e[1], e[0]-a/b*e[1], e[2]]; } } unittest { import std.numeric : gcd; foreach (i; 0..100) { foreach (j; 0..100) { auto e = extGcd(i, j); assert(e[2] == gcd(i, j)); assert(e[0] * i + e[1] * j == e[2]); } } }