import java.util.*;
import java.io.*;
import java.lang.Math;

public class Main {
    public static long MOD = 1000000007;
    public static void main(String[] args) throws IOException {

        PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

        //int t = sc.nextInt();
        //while(t -- > 0) {
        //
        //    if(t > 0) {
        //        aa('\n');
        //    }
        //}
        out.close();
        return;
    }

    public static long pow(long x, long y) {
        long ret = 1;
        while(y > 0) {
            if((y & 1) == 1) {
                ret = (ret * x) % MOD;
            }
            x = (x * x) % MOD;
            y >>= 1;
        }
        return ret;
    }

    public static String arr2str(long[] arr) {
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < arr.length - 1; i ++) {
            sb.append(arr[i]);
            sb.append(' ');
        }
        sb.append(arr[arr.length - 1]);
        return sb.toString();
    }

    public static void readArr(long[] arr) {
        for(int i = 0; i < arr.length; i ++) {
            arr[i] = sc.nextLong();
        }
    }

    public static void readArr(int[] arr) {
        for(int i = 0; i < arr.length; i ++) {
            arr[i] = sc.nextInt();
        }
    }

    public static void readMatrix(long[][] m) {
        for(int i = 0; i < m.length; i ++) {
            for(int j = 0; j < m[0].length; j ++) {
                m[i][j] = sc.nextLong();
            }
        }
    }

    public static void readMatrix(int[][] m) {
        for(int i = 0; i < m.length; i ++) {
            for(int j = 0; j < m[0].length; j ++) {
                m[i][j] = sc.nextInt();
            }
        }
    }

    // divide x => multiply inverse(x)
    public static long inverse(long x) {
        return pow(x, MOD - 2);
    }

    InputReader sc = new InputReader(System.in);
}

class InputReader {
    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;
    private SpaceCharFilter filter;

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

    public 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++];
    }

    public int nextInt() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        int res = 0;
        do {
            if (c < '0' || c > '9') {
                throw new InputMismatchException();
            }
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }

    public long nextLong() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        long res = 0;
        do {
            if (c < '0' || c > '9') {
                throw new InputMismatchException();
            }
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }

    public String nextString() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        StringBuilder res = new StringBuilder();
        do {
            if (Character.isValidCodePoint(c)) {
                res.appendCodePoint(c);
            }
            c = read();
        } while (!isSpaceChar(c));
        return res.toString();
    }

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

    public static String[] readStringArray(InputReader in, int size) {
        String[] array = new String[size];
        for (int i = 0; i < size; i++)
            array[i] = in.nextString();
        return array;
    }

    public static String[][] readStringTable(InputReader in, int rowCount, int columnCount) {
        String[][] table = new String[rowCount][];
        for (int i = 0; i < rowCount; i++)
            table[i] = readStringArray(in, columnCount);
        return table;
    }

    public char nextChar() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        return (char) c;
    }

    public String nextLine() {
        int c = read();
        while (isSpaceChar2(c))
            c = read();
        StringBuilder res = new StringBuilder();
        do {
            if (Character.isValidCodePoint(c)) {
                res.appendCodePoint(c);
            }
            c = read();
        } while (!isSpaceChar2(c));
        return res.toString();
    }

    public double readDouble() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        double res = 0;
        while (!isSpaceChar(c) && c != '.') {
            if (c == 'e' || c == 'E') {
                return res * Math.pow(10, nextInt());
            }
            if (c < '0' || c > '9') {
                throw new InputMismatchException();
            }
            res *= 10;
            res += c - '0';
            c = read();
        }
        if (c == '.') {
            c = read();
            double m = 1;
            while (!isSpaceChar(c)) {
                if (c == 'e' || c == 'E') {
                    return res * Math.pow(10, nextInt());
                }
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                m /= 10;
                res += (c - '0') * m;
                c = read();
            }
        }
        return res * sgn;
    }

    public boolean isSpaceChar(int c) {
        if (filter != null) {
            return filter.isSpaceChar(c);
        }
        return isWhitespace(c);
    }

    public boolean isSpaceChar2(int c) {
        if (filter != null) {
            return filter.isSpaceChar2(c);
        }
        return isWhitespace2(c);
    }

    public static boolean isWhitespace2(int c) {
        return c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    public static boolean isWhitespace(int c) {
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    public interface SpaceCharFilter {
        public boolean isSpaceChar(int ch);

        public boolean isSpaceChar2(int ch);
    }

}