using System; using System.Collections.Generic; using System.Linq; using Debug = System.Diagnostics.Debug; using Watch = System.Diagnostics.Stopwatch; using StringBuilder = System.Text.StringBuilder; using System.Numerics; using System.Threading.Tasks; #region Ex static class Ex { //static public string AsString(this IEnumerable ie) { return new string(System.Linq.Enumerable.ToArray(ie)); } //static public string AsJoinedString(this IEnumerable ie, string st = " ") { return string.Join(st, ie); } static public void Main() { Console.OpenStandardInput().Read(buf, 0, 32); var n = Long(); var p = Integer(); var c = Integer(); var a = new int[] { 2, 3, 5, 7, 11, 13 }; var b = new int[] { 4, 6, 8, 9, 10, 12 }; var max = 13 * p + 12 * c; const int w = 13 * 50 + 1; const int h = 12 * 50 + 1; const ulong mod = (long)1e9 + 7; var C = new ulong[max + 1]; var A = new ulong[51 * (13 * 50 + 1)]; var B = new ulong[51 * (12 * 50 + 1)]; A[0] = B[0] = 1; for (int k = 0; k < 6; k++) for (int i = 0; i < 50; i++) for (int j = 0; j < w; j++) if (A[i * w + j] > 0) A[(i + 1) * w + j + a[k]] += A[i * w + j]; for (int k = 0; k < 6; k++) for (int i = 0; i < 50; i++) for (int j = 0; j < h; j++) if (B[i * h + j] > 0) B[(i + 1) * h + j + b[k]] += B[i * h + j]; for (int i = 0; i < w; i++) if (A[p * w + i] > 0) for (int j = 0; j < h; j++) if (B[c * h + j] > 0) C[i + j] = ((C[i + j] + A[p * w + i] * B[c * h + j]) % mod); Polynomial.k = max; Polynomial.C = C; Polynomial.st = 2 * p + 4 * c; var res = (long)(Polynomial.Get(n + max - 1) % mod); if (10000000000 <= res) goto l10000000000; if (1000000000 <= res) goto l1000000000; if (100000000 <= res) goto l100000000; if (10000000 <= res) goto l10000000; if (1000000 <= res) goto l1000000; if (100000 <= res) goto l100000; if (10000 <= res) goto l10000; if (1000 <= res) goto l1000; if (100 <= res) goto l100; if (10 <= res) goto l10; goto l1; l10000000000: buf[wp++] = (byte)('0' + Math.DivRem(res, 10000000000, out res)); l1000000000: buf[wp++] = (byte)('0' + Math.DivRem(res, 1000000000, out res)); l100000000: buf[wp++] = (byte)('0' + Math.DivRem(res, 100000000, out res)); l10000000: buf[wp++] = (byte)('0' + Math.DivRem(res, 10000000, out res)); l1000000: buf[wp++] = (byte)('0' + Math.DivRem(res, 1000000, out res)); l100000: buf[wp++] = (byte)('0' + Math.DivRem(res, 100000, out res)); l10000: buf[wp++] = (byte)('0' + Math.DivRem(res, 10000, out res)); l1000: buf[wp++] = (byte)('0' + Math.DivRem(res, 1000, out res)); l100: buf[wp++] = (byte)('0' + Math.DivRem(res, 100, out res)); l10: buf[wp++] = (byte)('0' + Math.DivRem(res, 10, out res)); l1: buf[wp++] = (byte)('0' + res); buf[wp++] = (byte)'\n'; Console.OpenStandardOutput().Write(buf, 0, wp); } static readonly byte[] buf = new byte[32]; static int rp = 0; static int wp = 0; static public int Integer() { var ret = 0; const byte zr = 48, nn = 57; while (buf[rp] >= zr && buf[rp] <= nn) ret = ret * 10 + buf[rp++] - zr; rp++; return ret; } static public long Long() { long ret = 0; const byte zr = 48, nn = 57; while (buf[rp] >= zr && buf[rp] <= nn) ret = ret * 10 + buf[rp++] - zr; rp++; return ret; } } #endregion #region Polynomial static public class Polynomial { const ulong mod = (ulong)1e9 + 7; static public int k; static public ulong[] C = new ulong[1251]; static public int st; static readonly ulong[] p = new ulong[1250]; static readonly ulong[] ret = new ulong[1250]; static public ulong Get(long n) { p[1] = ret[0] = 1; var count = 0; if (k < 800) { for (; n > 0; n >>= 1) { if ((n & 1) == 1) multiply(); multiply_self(); //var now = sw.ElapsedMilliseconds; Program.IO.Printer.Out.WriteLine("{0} {1}", (n & 1), now - last); sum += now - last; last = now; cnt++; } } else { var t = 1; //long sum = 0; var cnt = 0; long last = 0; var sw = new System.Diagnostics.Stopwatch(); sw.Start(); for (; n > 0 && count < 10; count++, n >>= 1) { if ((n & 1) == 1) multiply_simple(t); p[t << 1] = 1; p[t] = 0; t <<= 1; //var now = sw.ElapsedMilliseconds; Program.IO.Printer.Out.WriteLine("{0} {1}", (n & 1), now - last); sum += now - last; last = now; cnt++; } for (; n > 1; n >>= 1) { if ((n & 1) == 1) multiply(); multiply_self(); //var now = sw.ElapsedMilliseconds; Program.IO.Printer.Out.WriteLine("{0} {1}", (n & 1), now - last); sum += now - last; last = now; cnt++; } if (n == 1) multiply(); } //sw.Stop(); Program.IO.Printer.Out.WriteLine("{0} {1}", 1.0 * sum / cnt, cnt); ulong ans = 0; for (int i = 0; i < k; i++) ans += ret[i]; return ans; } static readonly ulong[] temp = new ulong[2500]; static void multiply() { Array.Clear(temp, 0, 2500); for (int i = 0; i < k; i++) { if (ret[i] == 0) continue; for (int j = 0; j < k; j += 2) { temp[i + j] = (temp[i + j] + ret[i] * p[j]) % mod; temp[i + j + 1] = (temp[i + j + 1] + ret[i] * p[j + 1]) % mod; } } for (int i = (k << 1) - 1; i >= k; i--) for (int j = st; j <= k; j++) temp[i - j] = (temp[i - j] + temp[i] * C[j]) % mod; Buffer.BlockCopy(temp, 0, ret, 0, sizeof(ulong) * k); } static void multiply_simple(int t) { Array.Clear(temp, 0, 1250); for (int i = 0; i < k; i++) { if (ret[i] == 0) continue; temp[i + t] = temp[i + t] + ret[i] * p[t]; } Buffer.BlockCopy(temp, 0, ret, 0, sizeof(ulong) * k); } static void multiply_self() { Array.Clear(temp, 0, 2500); for (int i = 0; i < k; i += 2) { for (int j = 0; j < k; j += 2) { temp[i + j] = (temp[i + j] + p[i] * p[j]) % mod; temp[i + j + 1] = (temp[i + j + 1] + p[i] * p[j + 1]) ;//% mod; } for (int j = 0; j < k; j += 2) { temp[i + 1 + j] = (temp[i + 1 + j] + p[i + 1] * p[j]) % mod; temp[i + j + 2] = (temp[i + j + 2] + p[i + 1] * p[j + 1]) % mod; } } for (int i = (k << 1) - 1; i >= k; i--) { for (var j = st; j <= k; j++) temp[i - j] = (temp[i - j] + temp[i] * C[j]) % mod; } Buffer.BlockCopy(temp, 0, p, 0, sizeof(ulong) * k); } } #endregion