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

public class Day2I {
    FastScanner in;
    PrintWriter out;

    final long md = 1000000007;

    long add(long a, long b, long c) {
        long res = (a % c + b % c) % c;
        if (res < 0)
            res += c;
        return res;
    }

    long sub(long a, long b, long c) {
        long res = (a % c - b % c) % c;
        if (res < 0)
            res += c;
        return res;
    }

    long mul(long a, long b, long c) {
        a %= c;
        b %= c;
        if (a < 0)
            a += c;
        if (b < 0)
            b += c;
        long res = 0;
        while (b > 0) {
            if ((b & 1) == 1) {
                res = add(res, a, c);
            }
            a = add(a, a, c);
            b >>= 1;
        }
        return res % c;
    }

    long power(long a, long b, long c) {
        long res = 1;
        while (b > 0) {
            if ((b & 1) != 0) {
                res = mul(res, a, c);
            }
            a = mul(a, a, c);
            b >>= 1;
        }
        return res % c;
    }

    long inverse(long a, long p) {
        return power(a, p - 2, p);
    }

    long get_sum(long a, long cnt, long p) {
        if (cnt == 0) {
            return 0;
        }
        if (cnt == 1) {
            return 1;
        }
        long u = get_sum(a, cnt / 2, p);
        u = mul(u, power(a, cnt / 2, p) + 1, p);
        if (cnt % 2 == 1) {
            u = add(mul(u, a, p), 1, p);
        }
        return u;
    }

    long divide_power(long a, long b, long p, long md) {
        if (p != md) {
            long rem = power(a, b, p);
            long value = sub(power(a, b, md), rem, md);
            value = mul(value, inverse(p, md), md);
            return value;
        }
        return power(a, b, md * md) / md;
    }

    long divide_product(long a, long b, long p, long md) {
        if (p != md) {
            long rem = mul(a, b, p);
            long value = sub(mul(a, b, md), rem, md);
            value = mul(value, inverse(p, md), md);
            return value;
        }
        return mul(a, b, md * md) / md;
    }

    long divide_sum_and_product(long x, long a, long b, long p, long md) {
        if (p != md) {
            long rem = add(x, mul(a, b, p), p);
            long value = sub(add(x, mul(a, b, md), md), rem, md);
            value = mul(value, inverse(p, md), md);
            return value;
        }
        return add(x, mul(a, b, md * md), md * md) / md;
    }

    long such_solve(long x, long p, long step, long r1, long r2) {
        if (r1 == 0 || r2 == 0) {
            return 0;
        }
        if (step == 0) {
            return (x < r2 ? r1 : 0);
        }
        long ans = 0;
        long t = Math.min(r1 - 1, (p - x - 1) / step);
        if (x < r2) {
            ans = add(Math.min(t, (r2 - x - 1) / step), 1, md);
        }
        x = add(x, mul(t + 1, step, p), p);
        r1 -= (t + 1);
        if (r1 == 0) {
            return ans;
        }
        long last = add(x, mul(r1 - 1, step, p), p);
        long after = last / step + 1;
        ans = add(ans, after, md);
        if (last >= r2) {
            ans = sub(ans, (last - r2) / step + 1, md);
        }
        r1 -= after;
        if (r1 == 0) {
            return ans;
        }
        long rounds = BigInteger.valueOf(x).add(BigInteger.valueOf(r1).multiply(BigInteger.valueOf(step))).divide(BigInteger.valueOf(p)).longValue();
        long small = such_solve(x, step, sub(step, p % step, step), rounds, r2
                % step);
        ans = add(ans, mul(small, r2 / step + 1, md), md);
        ans = add(ans, mul(rounds - small, r2 / step, md), md);
        return ans;
    }

    long solve_real_problem(long c1, long c2, long x, long p, long r1, long r2) {
        long c2inv = inverse(c2, p);
        c1 = mul(c1, c2inv, p);
        x = mul(x, c2inv, p);
        long step = sub(p, c1, p);
        long res = such_solve(x, p, step, r1, r2);
        return res;
    }

    long mySolve(long p, long x, long _L, long _R, long k) {
        long len = _R - _L + 1;
        long c1 = get_sum(power(2, k, p), len / k + 1, p);
        long c2 = mul(get_sum(power(2, k, p), len / k, p),
                power(2, len % k, p), p);
        if (c1 == 0 && c2 == 0) {
            long ans = 0;
            if (x == 0) {
                ans = power(2, k, md);
            }
            return ans;
        }
        if (c1 == 0) {
            long bmod = mul(x, inverse(c2, p), p);
            long bcnt = divide_power(2, k - len % k, p, md);
            long rem = power(2, k - len % k, p);
            if (bmod < rem) {
                bcnt++;
            }
            long ans = mul(power(2, len % k, md), bcnt, md);
            return ans;
        }
        if (c2 == 0) {
            long amod = mul(x, inverse(c1, p), p);
            long acnt = divide_power(2, len % k, p, md);
            long rem = power(2, len % k, p);
            if (amod < rem) {
                acnt++;
            }
            long ans = mul(acnt, power(2, k - len % k, md), md);
            return ans;
        }
        long r1 = power(2, len % k, p);
        long r2 = power(2, k - len % k, p);
        long ans = divide_power(2, k, p, md);
        ans = sub(ans, divide_product(r1, r2, p, md), md);
        ans = add(ans, solve_real_problem(c1, c2, x, p, r1, r2), md);
        return ans;
    }

    long stupid(long p, long x, long l, long r, long k) {
        long res = 0;
        for (int st = 0; st < 1 << k; st++) {
            String t = "";
            for (int i = 0; i < k; i++) {
                if (((1 << i) & st) != 0) {
                    t = t + "1";
                } else {
                    t = t + "0";
                }
            }
            String s = "";
            while (s.length() <= r) {
                s += t;
            }
            s = s.substring((int) l, (int) r + 1);
            long value = 0;
            for (int i = 0; i < s.length(); i++) {
                value = value * 2 + (s.charAt(i) - '0');
                value %= p;
            }
            if (value == x) {
                res++;
            }
        }
        return res;
    }

    void solve5555() {
        Random rnd = new Random(123);
        for (int it = 0; it < 123123; it++) {
            System.err.println("iter = " + it);
            final int MAX = (int) 1e9;
            long a = (long) (rnd.nextInt(MAX) * 1e9 + rnd.nextInt(MAX));
            long b = (long) (rnd.nextInt(MAX) * 1e9 + rnd.nextInt(MAX));
            long p = (long) (rnd.nextInt(MAX) * 1e9 + rnd.nextInt(MAX));
            long x = (long) (rnd.nextInt(MAX) * 1e9 + rnd.nextInt(MAX));
            p = BigInteger.valueOf(p).nextProbablePrime().longValue();
            long res = divide_sum_and_product(x, a, b, p, md);
            long correct = BigInteger.valueOf(a)
                    .multiply(BigInteger.valueOf(b)).add(BigInteger.valueOf(x))
                    .divide(BigInteger.valueOf(p)).mod(BigInteger.valueOf(md))
                    .longValue();
            if (res != correct) {
                System.err.println("res = " + res);
                System.err.println("correct = " + correct);
                throw new AssertionError();
            }
        }
    }

    void solve333333() {
        Random rnd = new Random(123);
        for (int it = 0; it < 123123; it++) {
            System.err.println("iter = " + it);
            final int MAX = 100;
            long a = 1 + rnd.nextInt(MAX);
            long cnt = 1 + rnd.nextInt(MAX);
            long p = (long) (rnd.nextInt(MAX) * 1e9 + rnd.nextInt(MAX));
            p = BigInteger.valueOf(p).nextProbablePrime().longValue();
            long res = get_sum(a, cnt, p);
            BigInteger corr = BigInteger.ZERO;
            BigInteger mul = BigInteger.ONE;
            for (int i = 0; i < cnt; i++) {
                corr = corr.add(mul);
                mul = mul.multiply(BigInteger.valueOf(a));
            }
            long correct = corr.mod(BigInteger.valueOf(p)).longValue();
            if (res != correct) {
                System.err.println("a = " + a + ", cnt = " + cnt + ", p = " + p);
                System.err.println("res = " + res);
                System.err.println("correct = " + correct);
                throw new AssertionError();
            }
        }
    }

    void solve12322() {
        Random rnd = new Random(123);
        for (int it = 0; it < 123123; it++) {
            System.err.println("iters = " + it);
            final int MAX = (int) 1e9;
            long a = (long) (rnd.nextInt(MAX) * 1e9 + rnd.nextInt(MAX));
            long b = rnd.nextInt(1000) + 1;//(long) (rnd.nextInt(MAX) * 1e9 + rnd.nextInt(MAX));
            long p = (long) (rnd.nextInt(MAX) * 1e9 + rnd.nextInt(MAX));
            p = BigInteger.valueOf(p).nextProbablePrime().longValue();
            long res = divide_power(a, b, p, md);
            long correct = BigInteger
                    .valueOf(a)
                    .pow((int) b)
                    .divide(BigInteger.valueOf(p)).mod(BigInteger.valueOf(md)).longValue();
            if (res != correct) {
                System.err.println("res = " + res);
                System.err.println("correct = " + correct);
                throw new AssertionError();
            }
        }
    }

    void solv3e123() {
        Random rnd = new Random(123);
        final int MAX = 14;
        for (int it = 0; it < 123123; it++) {
            System.err.println("iter = " + it);
            int p = BigInteger.valueOf(3 + rnd.nextInt(MAX))
                    .nextProbablePrime().intValue();
            int x = rnd.nextInt(p);
            int l = rnd.nextInt(MAX), r = rnd.nextInt(MAX);
            if (r < l) {
                int tmp = l;
                l = r;
                r = tmp;
            }
            int k = 1 + rnd.nextInt(MAX);
            long my = mySolve(p, x, l, r, k);
            long stupid = stupid(p, x, l, r, k);
            if (my != stupid) {
                System.err.println("my = " + my);
                System.err.println("correct = " + stupid);
                throw new AssertionError();
            }
        }
    }

    void solve() {
        while (true) {
            long p = in.nextLong();
            long x = in.nextLong();
            long l = in.nextLong();
            long r = in.nextLong();
            long k = in.nextLong();
            if (p == 0) {
                break;
            }
            out.println(mySolve(p, x, l, r, k));
        }
    }

    void run() {
        try {
            in = new FastScanner(new File("object.in"));
            out = new PrintWriter(new File("object.out"));

            solve();

            out.close();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }

    void runIO() {

        in = new FastScanner(System.in);
        out = new PrintWriter(System.out);

        solve();

        out.close();
    }

    class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        public FastScanner(File f) {
            try {
                br = new BufferedReader(new FileReader(f));
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
        }

        public FastScanner(InputStream f) {
            br = new BufferedReader(new InputStreamReader(f));
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                String s = null;
                try {
                    s = br.readLine();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (s == null)
                    return null;
                st = new StringTokenizer(s);
            }
            return st.nextToken();
        }

        boolean hasMoreTokens() {
            while (st == null || !st.hasMoreTokens()) {
                String s = null;
                try {
                    s = br.readLine();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (s == null)
                    return false;
                st = new StringTokenizer(s);
            }
            return true;
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }
    }

    public static void main(String[] args) {
        new Day2I().runIO();
    }
}