public class Euler942 {
    static final long kOutMod = 1000000007L;

    public static String solve(int q) {
        int half = (q - 1) / 2;
        byte[] is_residue = new byte[q];
        long r = 1;
        for (int x = 1; x <= half; ++x) {
            is_residue[(int) r] = 1;
            r += 2L * x + 1L;
            if (r >= q) {
                r -= q;
            }
        }

        long pow2 = 1;
        long sum_nonres = 0;
        long signed_sum = 0;

        for (int n = 1; n < q; ++n) {
            pow2 = (pow2 * 2L) % kOutMod;
            if (is_residue[n] == 1) {
                signed_sum += pow2;
                if (signed_sum >= kOutMod) {
                    signed_sum -= kOutMod;
                }
            } else {
                if (signed_sum >= pow2) {
                    signed_sum -= pow2;
                } else {
                    signed_sum += kOutMod - pow2;
                }
                sum_nonres += pow2;
                if (sum_nonres >= kOutMod) {
                    sum_nonres -= kOutMod;
                }
            }
        }

        if ((q & 7) == 1) {
            return Long.toString((1L + 2L * sum_nonres) % kOutMod);
        }
        return Long.toString(signed_sum);
    }

    public static void main(String[] args) {
        if (!solve(5).equals("6") || !solve(17).equals("47569")) {
            System.out.println("Validation failed");
            return;
        }
        System.out.println(solve(74207281));
    }
}