Problem: Petya loves lucky numbers. Everybody knows that positive integers are lucky if their decimal representation doesn't contain digits other than 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

Lucky number is super lucky if it's decimal representation contains equal amount of digits 4 and 7. For example, numbers 47, 7744, 474477 are super lucky and 4, 744, 467 are not.

One day Petya came across a positive integer n. Help him to find the least super lucky number which is not less than n.

Input

The only line contains a positive integer n (1 ≤ n ≤ 10100000). This number doesn't have leading zeroes.

Output

Output the least super lucky number that is more than or equal to n.

Examples

Input

4500


Output

4747


Input

47


Output

47

Solution (in JAVA):

Solution:
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;

/**
 * P96B
 *
 * @author hemenghai
 * @date 2019/1/23 15:50
 */
public class Main {

    private static int cur, pos, sum, len;
    private static long max, min, ans, res;
    private static int ai, bi, ci, di;
    private static int[] aix, bix;
    private static long al, bl, cl, dl;
    private static long[] alx, blx;
    private static double ad, bd, cd, dd;
    private static double[] adx, bdx;
    private static boolean ab, bb, cb, db;
    private static boolean[] abx, bbx;
    private static boolean[][] abxx, bbxx;
    private static char ac, bc, cc, dc;
    private static char[] acx, bcx;
    private static String as, bs, cs, ds;
    private static InputReader in = new InputReader(System.in);
    private static PrintWriter out = new PrintWriter(System.out);

    public static void main(String[] args) {
        long n = in.nextLong();
        aix = new int[20];

        al = n;
        for (int i = 1; i <= 10; i++) {
            aix[i] = (int) (al % 10);
            al /= 10;
            if (aix[i] != 0) {
                pos = i;
            }
        }

        if (pos % 2 == 1) {
            pos += 1;
        }

        max = getMax(pos);
        if (n > max) {
            pos += 2;
        }
        out.println(getNextSuperLucky(pos));
        out.close();
    }

    private static long getNextSuperLucky(int pos) {
        toNextLucky(pos);
        int bitmask = 0;
        int half = pos / 2;
        int bit7 = 0;
        for (int i = pos; i > 0; i--) {
            bitmask <<= 1;
            if (aix[i] == 7) {
                bitmask += 1;
                bit7++;
            }
        }
        int value;
        while (bit7 != half) {
            bit7 = 0;
            bitmask += 1;
            value = bitmask;
            while (value != 0) {
                if ((value & 1) == 1) {
                    bit7++;
                }
                value >>= 1;
            }
        }
        for (int i = 1; i <= pos; i++) {
            if ((bitmask & 1) == 1) {
                aix[i] = 7;
            } else {
                aix[i] = 4;
            }
            bitmask >>= 1;
        }
        long res = 0;
        for (int i = pos; i > 0; i--) {
            res *= 10;
            res += aix[i];
        }
        return res;
    }

    private static void toNextLucky(int pos) {
        ab = false;
        for (int i = pos; i > 0; i--) {
            if (!ab) {
                if (aix[i] < 4) {
                    aix[i] = 4;
                    ab = true;
                } else if (aix[i] > 4 && aix[i] < 7) {
                    aix[i] = 7;
                    ab = true;
                } else if (aix[i] > 7) {
                    aix[i] = 4;
                    for (int j = i + 1; j <= pos; j++) {
                        if (aix[j] == 4) {
                            aix[j] = 7;
                            break;
                        } else if (aix[j] == 7) {
                            aix[j] = 4;
                        }
                    }
                    ab = true;
                }

            } else {
                aix[i] = 4;
            }
        }
    }

    private static long getMax(int pos) {
        long max = 0;
        for (int i = 1; i <= pos / 2; i++) {
            max *= 10;
            max += 7;
        }
        for (int i = pos / 2 + 1; i <= pos; i++) {
            max *= 10;
            max += 4;
        }
        return max;
    }

    private static class InputReader {

        private static final char MINUS = '-';
        private static final char POINT = '.';
        private static final char ZERO = '0';

        private InputStream stream;

        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public String next() {
            return readString();
        }

        public int nextInt() {
            return (int) nextLong();
        }

        public long nextLong() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == MINUS) {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                res *= 10;
                res += c - ZERO;
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public double nextDouble() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == MINUS) {
                sgn = -1;
                c = read();
            }
            double res = 0;
            while (!isSpaceChar(c) && c != POINT) {
                if (c == 'e' || c == 'E') {
                    return res * Math.pow(10, nextInt());
                }
                res *= 10;
                res += c - ZERO;
                c = read();
            }
            if (c == POINT) {
                c = read();
                double m = 1.0D;
                while (!isSpaceChar(c)) {
                    if (c == 'e' || c == 'E') {
                        return res * Math.pow(10, nextInt());
                    }
                    m /= 10;
                    res += (c - ZERO) * m;
                    c = read();
                }
            }
            return res * sgn;
        }

        private boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        private String readString() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        private int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }
    }
}