import java.util.Arrays;
import java.util.PriorityQueue;

public class Euler718 {
    static final long kMod = 1000000007L;

    static long powU64(long base, int exp) {
        long result = 1;
        while (exp > 0) {
            if ((exp & 1) != 0) {
                result *= base;
            }
            base *= base;
            exp >>= 1;
        }
        return result;
    }

    static long modPow(long base, long exp) {
        long result = 1;
        base %= kMod;
        while (exp > 0) {
            if ((exp & 1) != 0) {
                result = (result * base) % kMod;
            }
            base = (base * base) % kMod;
            exp >>= 1;
        }
        return result;
    }

    static class Node implements Comparable<Node> {
        long d;
        int u;

        Node(long d, int u) {
            this.d = d;
            this.u = u;
        }

        @Override
        public int compareTo(Node other) {
            return Long.compare(this.d, other.d);
        }
    }

    public static String solve() {
        int p = 6;
        long A = powU64(17, p);
        long B = powU64(19, p);
        long C = powU64(23, p);

        long[] dist = new long[(int) A];
        Arrays.fill(dist, Long.MAX_VALUE / 4);

        PriorityQueue<Node> pq = new PriorityQueue<>();
        dist[0] = 0;
        pq.add(new Node(0, 0));

        while (!pq.isEmpty()) {
            Node node = pq.poll();
            long d = node.d;
            int u = node.u;

            if (d != dist[u]) {
                continue;
            }

            int v = (int) ((u + B) % A);
            long nd = d + B;
            if (nd < dist[v]) {
                dist[v] = nd;
                pq.add(new Node(nd, v));
            }

            v = (int) ((u + C) % A);
            nd = d + C;
            if (nd < dist[v]) {
                dist[v] = nd;
                pq.add(new Node(nd, v));
            }
        }

        long sumWMod = 0;
        long sumW2Mod = 0;
        for (long w : dist) {
            long wm = w % kMod;
            sumWMod = (sumWMod + wm) % kMod;
            sumW2Mod = (sumW2Mod + (wm * wm) % kMod) % kMod;
        }

        long inv2 = (kMod + 1) / 2;
        long inv12 = modPow(12, kMod - 2);
        long Am = A % kMod;
        long invA = modPow(Am, kMod - 2);

        long genus = (sumWMod * invA) % kMod;
        genus = (genus + kMod - (((Am + kMod - 1) % kMod * inv2) % kMod)) % kMod;

        long gaps = (sumW2Mod * inv2) % kMod;
        gaps = (gaps * invA) % kMod;
        gaps = (gaps + kMod - ((sumWMod * inv2) % kMod)) % kMod;
        long A2m = (Am * Am) % kMod;
        gaps = (gaps + (((A2m + kMod - 1) % kMod * inv12) % kMod)) % kMod;

        long shift = (A % kMod + B % kMod + C % kMod) % kMod;
        long tri = (shift * ((shift + kMod - 1) % kMod) % kMod * inv2) % kMod;

        long ans = tri;
        ans = (ans + (genus * shift) % kMod) % kMod;
        ans = (ans + gaps) % kMod;

        return Long.toString(ans);
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}