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.*;
import java.math.*;
import java.util.*;


// author @mdazmat9
public  class codeforces{
    static   ArrayList<String > list=new ArrayList<>();
    static   ArrayList<Long > answer=new ArrayList<>();
    static HashSet set=new HashSet();
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int test = 1;
        for (int ind = 0; ind < test; ind++) {
            int n=sc.nextInt();
            permute("47",0,1);
            permute("4477",0,3);
            permute("444777",0,5);
            permute("44447777",0,7);
            permute("4444477777",0,9);


            for(int i=0;i<list.size();i++){
                answer.add(Long.parseLong(list.get(i)));
            }
            Collections.sort(answer);
            if(set.contains(n+"")){
                out.println(n);
            }
            else
            out.println(answer.get(leastgreater(0,(answer.size()-1) ,n)));
        }
        out.flush();
    }
   static int leastgreater(int low, int high, int key)
    {
        int ans = -1;

        while (low <= high) {
            int mid = low + (high - low + 1) / 2;
            long midVal = answer.get(mid);

            if (midVal < key) {

                // if mid is less than key, all elements
                // in range [low, mid - 1] are <= key
                // then we search in right side of mid
                // so we now search in [mid + 1, high]
                low = mid + 1;
            }
            else if (midVal > key) {

                // if mid is greater than key, all elements
                // in range [mid + 1, high] are >= key
                // we note down the last found index, then
                // we search in left side of mid
                // so we now search in [low, mid - 1]
                ans = mid;
                high = mid - 1;
            }
            else if (midVal == key) {

                // if mid is equal to key, all elements in
                // range [low, mid] are <= key
                // so we now search in [mid + 1, high]
                low = mid + 1;
            }
        }

        return ans;
    }

    private static void permute(String str, int l, int r)
    {
        if (l == r) {
            if(!set.contains(str))
            list.add(str);
            set.add(str);
        }
        else
        {
            for (int i = l; i <= r; i++)
            {
                str = swap(str,l,i);
                permute(str, l+1, r);
                str = swap(str,l,i);
            }
        }
    }
    public static String swap(String a, int i, int j)
    {
        char temp;
        char[] charArray = a.toCharArray();
        temp = charArray[i] ;
        charArray[i] = charArray[j];
        charArray[j] = temp;
        return String.valueOf(charArray);
    }



    static   void shuffle(int[] a) {
        int n = a.length;
        for(int i = 0; i < n; i++) {
            int r = i + (int) (Math.random() * (n - i));
            int tmp = a[i];
            a[i] = a[r];
            a[r] = tmp;
        }
    }
    static long gcd(long a , long b)
    {
        if(b == 0)
            return a;
        return gcd(b , a % b);
    }

}
class Scanner {
    public BufferedReader reader;
    public StringTokenizer st;

    public Scanner(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream));
        st = null;
    }

    public String next() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                String line = reader.readLine();
                if (line == null) return null;
                st = new StringTokenizer(line);
            } catch (Exception e) {
                throw (new RuntimeException());
            }
        }
        return st.nextToken();
    }

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

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

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

class OutputWriter {
    BufferedWriter writer;

    public OutputWriter(OutputStream stream) {
        writer = new BufferedWriter(new OutputStreamWriter(stream));
    }

    public void print(int i) throws IOException {
        writer.write(i);
    }

    public void print(String s) throws IOException {
        writer.write(s);
    }

    public void print(char[] c) throws IOException {
        writer.write(c);
    }

    public void close() throws IOException {
        writer.close();
    }

}