import java.io.*;
import java.util.*;
import java.math.*;

public class F {
    public static void main(String[] args) throws IOException {
        new F().run();
    }

    void run() throws IOException {
        //Scanner in = new Scanner(System.in);
        //PrintWriter out = new PrintWriter(System.out);
        Scanner in = new Scanner(new File("oranges.in"));
        PrintWriter out = new PrintWriter(new File("oranges.out"));
        BigInteger p, n;
        p = in.nextBigInteger();
        n = in.nextBigInteger();

        BigInteger start = BigInteger.ONE;
        int k = -1;
        for (int i = 0; ; ++i) {
            if (start.compareTo(n) > 0) {
                k = i - 1;
                //out.println(i);
                start = start.divide(p);
                break;
            }
            start = start.multiply(p);
        }

        BigInteger res1, res2, res3;
        res1 = BigInteger.ZERO;
        res2 = BigInteger.ZERO;
        res3 = BigInteger.ZERO;

        //out.println(start);
        //out.println(k);

        {
            BigInteger A = n.subtract(start);
            long a[] = new long [5000];
            for (int i = 0; i < 5000; ++i) {
                a[i] = 0;
            }

            //out.print(A + " ");

            int index = 0;
            while (A.compareTo(BigInteger.ZERO) > 0) {
                a[index ++] = (A.remainder(p)).longValue();
                A = A.divide(p);
            }



            int last_non_zero = -1;
            for (int i = 0; i < 5000; ++i)
                if (a[i] != 0) last_non_zero = i;
            if (last_non_zero == -1) {
                res1 = BigInteger.valueOf(k);
            } else {
                long q = p.longValue();
                long coef = 1;
                for (int i = 0; i + 1 <= last_non_zero; ++i)
                    if (a[i] > 0) {
                        a[i] -= q;
                        if (a[i] < -2) coef = 0;
                        ++a[i + 1];

                        if (a[i] == -1) {
                            coef *= 2L;
                            coef %= 1000000007L;
                        }
                    }
                if (a[last_non_zero] == 1 && last_non_zero < k) res1 = res1.add(BigInteger.valueOf(coef));
                for (int i = last_non_zero; i + 1 <= k - 1; ++i) {
                    a[i] -= q;
                    if (a[i] < -2) coef = 0;
                    ++a[i + 1];
                    if (a[i] == -1) {
                        coef *= 2L;
                        coef %= 1000000007L;
                    }
                    if (a[i + 1] == 1) res1 = res1.add(BigInteger.valueOf(coef));
                }
            }
        }

        {
            BigInteger A = start.add(start).subtract(n);
            if (A.compareTo(BigInteger.ZERO) <= 0) {
            } else {
                long a[] = new long [5000];
                for (int i = 0; i < 5000; ++i) {
                    a[i] = 0;
                }

                int index = 0;
                while (A.compareTo(BigInteger.ZERO) > 0) {
                    a[index ++] = (A.remainder(p)).longValue();
                    A = A.divide(p);
                }

                int ones = 0;
                for (int i = 0; i < 5000; ++i)
                    if (a[i] == 1) ++ones;

                if (ones != 0) {
                    int last_non_zero = -1;
                    for (int i = 0; i < 5000; ++i)
                        if (a[i] != 0) last_non_zero = i;

                    long coef = 1;
                    int d = -1;
                    for (int i = 0; i < 5000; ++i)
                        if (a[i] > 2) coef = 0; else {
                            if (a[i] == 1) {
                                ++d;
                                coef *= 2L;
                                coef %= 1000000007L;
                            }
                        }
                    if (coef != 0 && last_non_zero <= k - 1) {
                        coef = 1;
                        for (int i = 0; i < d; ++i) {
                            coef *= 2L;
                            coef %= 1000000007L;
                        }
                        res2 = BigInteger.valueOf(coef);
                    }
                    //if (last_non_zero <= k - 1) {
                        //res2 = BigInteger.valueOf(coef);
                    //}
                }
            }
        }

        {
            BigInteger A = (start.multiply(p)).subtract(n);
            long a[] = new long [5000];
            for (int i = 0; i < 5000; ++i) {
                a[i] = 0;
            }

            //out.println(A);
            //out.println(k);
            int index = 0;
            while (A.compareTo(BigInteger.ZERO) > 0) {
                a[index ++] = (A.remainder(p)).longValue();
                A = A.divide(p);
            }

            int last_non_zero = -1;
            for (int i = 0; i < 5000; ++i)
                if (a[i] != 0) last_non_zero = i;

            long coef = 1;
            int zero = 0;
            for (int i = 0; i < k + 1; ++i) {
                if (a[i] == 1) {
                    coef *= 2L;
                    coef %= 1000000007L;
                }
                if (a[i] > 2) {
                    coef = 0;
                }
                if (a[i] == 0) ++zero;
            }
            coef *= (long)(zero);
            coef %= 1000000007L;
            long coef3 = 1;
            int nice[] = new int [5000];
            for (int i = 0; i < 5000; ++i)
                nice[i] = 1;
            for (int i = k; i >= 0; --i) {
                if (nice[i + 1] == 0) nice[i] = 0;
                if (a[i] > 1) nice[i] = 0;
            }
            for (int i = 0; i < k + 1; ++i) {
                if (a[i] == 0) {
                    if (last_non_zero <= k && nice[i + 1] == 1)
                        res3 = res3.add(BigInteger.valueOf(coef3));
                }
                if (a[i] == 1) {
                    coef3 *= 2L;
                    coef3 %= 1000000007L;
                }
            }

            //out.println(res3);
            //res3 = res3.add(BigInteger.valueOf(coef));
            if (last_non_zero == -1) {
            } else {
                long q = p.longValue();
                long coef2 = 1;
                //a[last_non_zero] -= q;
                //++a[last_non_zero + 1];

                for (int i = 0; i < 5000; ++i)
                    nice[i] = 1;
                for (int i = k; i >= 0; --i) {
                    if (nice[i + 1] == 0) nice[i] = 0;
                    if (a[i] > 1) nice[i] = 0;
                }

                for (int i = 0; i <= last_non_zero; ++i) {
                    if (a[i] == q - 1 && a[i + 1] == 0 && nice[i + 1] == 1) {
                        if (i == last_non_zero) {
                            if (last_non_zero + 1 <= k)
                                res3 = res3.add(BigInteger.valueOf(coef2));
                        } else {
                            if (last_non_zero <= k)
                                res3 = res3.add(BigInteger.valueOf(coef2));
                        }
                    }
                    if (a[i] > 2) coef2 = 0;
                    if (a[i] == 1) {
                        coef2 *= 2L;
                        coef2 %= 1000000007L;
                    }
                }
                if (a[last_non_zero] != -1) coef2 = 0;

                //if (last_non_zero + 1 <= k)
                //    res3 = res3.add(BigInteger.valueOf(coef2));
            }
        }

        //out.println(res1);
        //out.println(res2);
        //out.println(res3);

        BigInteger res = res1.add(res2.add(res3));
        out.println(res.remainder(BigInteger.valueOf(1000000007L)));

        out.close();
    }
}