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

class FastIO implements AutoCloseable{ /*thanks 31536000*/
    private InputStream in;
    private final byte[] buffer = new byte[1024];
    private int read = 0;
    private int length = 0;
    private PrintWriter out;
    private PrintWriter err;
    private boolean autoFlush = false;
    private boolean outFlush = false;
    private boolean autoOutFlush = true;

    public FastIO() {
        this(System.in, System.out, System.err);
    }

    public FastIO(InputStream in, PrintStream out, PrintStream err) {
        this.in = in;
        this.out = new PrintWriter(out, false);
        this.err = new PrintWriter(err, false);
    }

    public final void setInputStream(InputStream in) {
        this.in = in;
    }

    public final void setInputStream(File in) {
        try {
            this.in = new FileInputStream(in);
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }

    public final void setOutputStream(PrintStream out) {
        this.out = new PrintWriter(out, false);
    }

    public final void setOutputStream(File out) {
        try {
            this.out = new PrintWriter(new FileOutputStream(out), false);
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }

    public final void setErrorStream(PrintStream err) {
        this.err = new PrintWriter(err, false);
    }

    public final void setErrorStream(File err) {
        try {
            this.err = new PrintWriter(new FileOutputStream(err), false);
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }

    public final void setAutoFlush(boolean flush) {
        autoFlush = flush;
    }

    public final void setAutoOutFlush(boolean flush) {
        autoOutFlush = flush;
    }

    private boolean hasNextByte() {
        if (read < length) return true;
        read = 0;
        try {
            length = in.read(buffer);
        } catch (IOException e) {
            e.printStackTrace();
        }
        return length > 0;
    }

    private byte readByte() {
        if (hasNextByte()) return buffer[read++];
        throw new NoSuchElementException();
    }

    private boolean readNewLine() {
        if (hasNextByte()) {
            if (buffer[read] == '\r') {
                ++ read;
                if (hasNextByte() && buffer[read] == '\n') ++ read;
                return true;
            }
            if (buffer[read] == '\n') {
                ++ read;
                return true;
            }
        }
        return false;
    }

    private static boolean isPrintableChar(byte c) {
        return 32 < c || c < 0;
    }

    private static boolean isNumber(int c) {
        return '0' <= c && c <= '9';
    }

    public final boolean hasNext() {
        while (hasNextByte() && !isPrintableChar(buffer[read])) read++;
        return hasNextByte();
    }

    public final char nextChar() {
        if (outFlush) {
            outFlush = false;
            flush();
        }
        byte b = readByte();
        if ((b & 0x80) == 0) return (char)b;
        if ((b & 0x20) == 0) return (char)((b & 0x1F) << 6 | (readByte() & 0x3F));
        return (char)((b & 0xF) << 12 | (readByte() & 0x3F) << 6 | (readByte() & 0x3F));
    }

    public final char[] nextChars() {
        return next().toCharArray();
    }

    public final char[] nextChars(char around) {
        return (around + next() + around).toCharArray();
    }

    public final char[][] nextChars(int height) {
        char[][] ret = new char[height][];
        for (int i = 0;i < ret.length;++ i) ret[i] = nextChars();
        return ret;
    }

    public final char[][] nextChars(int height, char around) {
        char[][] ret = new char[height + 2][];
        for (int i = 1;i <= height;++ i) ret[i] = nextChars(around);
        Arrays.fill(ret[0] = new char[ret[1].length], around);
        Arrays.fill(ret[ret.length - 1] = new char[ret[0].length], around);
        return ret;
    }

    public final String next() {
        if (outFlush) {
            outFlush = false;
            flush();
        }
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        do sb.append(nextChar()); while(hasNextByte() && isPrintableChar(buffer[read]));
        return sb.toString();
    }

    public final String nextLine() {
        if (outFlush) {
            outFlush = false;
            flush();
        }
        StringBuilder sb = new StringBuilder();
        while(!readNewLine()) sb.append(nextChar());
        return sb.toString();
    }

    public final long nextLong() {
        if (outFlush) {
            outFlush = false;
            flush();
        }
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        try {
            byte b = readByte();
            if (b == '-') {
                do n = n * 10 + '0' - b; while(isNumber(b = readByte()));
                return n;
            } else if (!isNumber(b)) throw new NumberFormatException();
            do n = n * 10 + b - '0'; while(isNumber(b = readByte()));
            return n;
        } catch (NoSuchElementException e) {
            return n;
        }
    }

    public final int nextInt() {
        if (outFlush) {
            outFlush = false;
            flush();
        }
        if (!hasNext()) throw new NoSuchElementException();
        int n = 0;
        try {
            byte b = readByte();
            if (b == '-') {
                do n = n * 10 + '0' - b; while(isNumber(b = readByte()));
                return n;
            } else if (!isNumber(b)) throw new NumberFormatException();
            do n = n * 10 + b - '0'; while(isNumber(b = readByte()));
            return n;
        } catch (NoSuchElementException e) {
            return n;
        }
    }

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

    public final int[] nextInt(int width) {
        int[] ret = new int[width];
        for (int i = 0;i < width;++ i) ret[i] = nextInt();
        return ret;
    }

    public final int[] nextInts() {
        return nextInts(" ");
    }

    public final int[] nextInts(String parse) {
        String[] get = nextLine().split(parse);
        int[] ret = new int[get.length];
        for (int i = 0;i < ret.length;++ i) ret[i] = Integer.valueOf(get[i]);
        return ret;
    }

    public final long[] nextLong(int width) {
        long[] ret = new long[width];
        for (int i = 0;i < width;++ i) ret[i] = nextLong();
        return ret;
    }

    public final long[] nextLongs() {
        return nextLongs(" ");
    }

    public final long[] nextLongs(String parse) {
        String[] get = nextLine().split(parse);
        long[] ret = new long[get.length];
        for (int i = 0;i < ret.length;++ i) ret[i] = Long.valueOf(get[i]);
        return ret;
    }

    public final int[][] nextInt(int width, int height) {
        int[][] ret = new int[height][width];
        for (int i = 0, j;i < height;++ i) for (j = 0;j < width;++ j) ret[i][j] = nextInt();
        return ret;
    }

    public final long[][] nextLong(int width, int height) {
        long[][] ret = new long[height][width];
        for (int i = 0, j;i < height;++ i) for (j = 0;j < width;++ j) ret[j][i] = nextLong();
        return ret;
    }

    public final boolean[] nextBoolean(char T) {
        char[] s = next().toCharArray();
        boolean[] ret = new boolean[s.length];
        for (int i = 0;i < ret.length;++ i) ret[i] = s[i] == T;
        return ret;
    }

    public final boolean[][] nextBoolean(char T, int height) {
        boolean[][] ret = new boolean[height][];
        for (int i = 0;i < ret.length;++ i) {
            char[] s = next().toCharArray();
            ret[i] = new boolean[s.length];
            for (int j = 0;j < ret[i].length;++ j) ret[i][j] = s[j] == T;
        }
        return ret;
    }

    @Override
    protected void finalize() throws Throwable {
        try {
            super.finalize();
        } finally {
            in.close();
            out.close();
            err.close();
        }
    }

    public final boolean print(boolean b) {
        out.print(b);
        if (autoFlush) flush();
        else outFlush = autoOutFlush;
        return b;
    }

    public final Object print(boolean b, Object t, Object f) {
        return b ? print(t) : print(f);
    }

    public final char print(char c) {
        out.print(c);
        if (autoFlush) flush();
        else outFlush = autoOutFlush;
        return c;
    }

    public final char[] print(char[] s) {
        out.print(s);
        if (autoFlush) flush();
        else outFlush = autoOutFlush;
        return s;
    }

    public final double print(double d) {
        out.print(d);
        if (autoFlush) flush();
        else outFlush = autoOutFlush;
        return d;
    }

    public final double print(double d, int length) {
        if (d < 0) {
            out.print('-');
            d = -d;
        }
        d += Math.pow(10, -length) / 2;
        out.print((long)d);
        out.print('.');
        d -= (long)d;
        for (int i = 0;i < length;++ i) {
            d *= 10;
            out.print((int)d);
            d -= (int)d;
        }
        if (autoFlush) flush();
        else outFlush = autoOutFlush;
        return d;
    }

    public final float print(float f) {
        out.print(f);
        if (autoFlush) flush();
        else outFlush = autoOutFlush;
        return f;
    }

    public final int print(int i) {
        out.print(i);
        if (autoFlush) flush();
        else outFlush = autoOutFlush;
        return i;
    }

    public final long print(long l) {
        out.print(l);
        if (autoFlush) flush();
        else outFlush = autoOutFlush;
        return l;
    }

    public final Object print(Object obj) {
        if (obj != null && obj.getClass().isArray()) {
            if (obj instanceof boolean[][]) print(obj, "\n", " ");
            else if (obj instanceof byte[][]) print(obj, "\n", " ");
            else if (obj instanceof short[][]) print(obj, "\n", " ");
            else if (obj instanceof int[][]) print(obj, "\n", " ");
            else if (obj instanceof long[][]) print(obj, "\n", " ");
            else if (obj instanceof float[][]) print(obj, "\n", " ");
            else if (obj instanceof double[][]) print(obj, "\n", " ");
            else if (obj instanceof char[][]) print(obj, "\n", " ");
            else if (obj instanceof Object[][]) print(obj, "\n", " ");
            else print(obj, " ");
        } else {
            out.print(obj);
            if (autoFlush) flush();
            else outFlush = autoOutFlush;
        }
        return obj;
    }

    public final String print(String s) {
        out.print(s);
        if (autoFlush) flush();
        else outFlush = autoOutFlush;
        return s;
    }

    public final Object print(Object array, String... parse) {
        print(array, 0, parse);
        if (autoFlush) flush();
        else outFlush = autoOutFlush;
        return array;
    }

    private final Object print(Object array, int check, String... parse) {
        if (check >= parse.length) {
            if (array != null && array.getClass().isArray()) throw new IllegalArgumentException("not equal dimension");
            print(array);
            return array;
        }
        String str = parse[check];
        if (array instanceof Object[]) {
            Object[] obj = (Object[]) array;
            if (obj.length == 0) return array;
            print(obj[0], check + 1, parse);
            for (int i = 1;i < obj.length;++ i) {
                print(str);
                print(obj[i], check + 1, parse);
            }
            return array;
        }
        if (array instanceof Collection) {
            Iterator<?> iter = ((Collection<?>)array).iterator();
            if (!iter.hasNext()) return array;
            print(iter.next(), check + 1, parse);
            while(iter.hasNext()) {
                print(str);
                print(iter.next(), check + 1, parse);
            }
            return array;
        }
        if (!array.getClass().isArray()) throw new IllegalArgumentException("not equal dimension");
        if (check != parse.length - 1) throw new IllegalArgumentException("not equal dimension");
        if (array instanceof boolean[]) {
            boolean[] obj = (boolean[]) array;
            if (obj.length == 0) return array;
            print(obj[0]);
            for (int i = 1;i < obj.length;++ i) {
                print(str);
                print(obj[i]);
            }
        } else if (array instanceof byte[]) {
            byte[] obj = (byte[]) array;
            if (obj.length == 0) return array;
            print(obj[0]);
            for (int i = 1;i < obj.length;++ i) {
                print(str);
                print(obj[i]);
            }
            return array;
        } else if (array instanceof short[]) {
            short[] obj = (short[]) array;
            if (obj.length == 0) return array;
            print(obj[0]);
            for (int i = 1;i < obj.length;++ i) {
                print(str);
                print(obj[i]);
            }
        } else if (array instanceof int[]) {
            int[] obj = (int[]) array;
            if (obj.length == 0) return array;
            print(obj[0]);
            for (int i = 1;i < obj.length;++ i) {
                print(str);
                print(obj[i]);
            }
        } else if (array instanceof long[]) {
            long[] obj = (long[]) array;
            if (obj.length == 0) return array;
            print(obj[0]);
            for (int i = 1;i < obj.length;++ i) {
                print(str);
                print(obj[i]);
            }
        } else if (array instanceof float[]) {
            float[] obj = (float[]) array;
            if (obj.length == 0) return array;
            print(obj[0]);
            for (int i = 1;i < obj.length;++ i) {
                print(str);
                print(obj[i]);
            }
        } else if (array instanceof double[]) {
            double[] obj = (double[]) array;
            if (obj.length == 0) return array;
            print(obj[0]);
            for (int i = 1;i < obj.length;++ i) {
                print(str);
                print(obj[i]);
            }
        } else if (array instanceof char[]) {
            char[] obj = (char[]) array;
            if (obj.length == 0) return array;
            print(obj[0]);
            for (int i = 1;i < obj.length;++ i) {
                print(str);
                print(obj[i]);
            }
        } else throw new AssertionError();
        return array;
    }

    public final Object[] print(String parse, Object... args) {
        print(args[0]);
        for (int i = 1;i < args.length;++ i) {
            print(parse);
            print(args[i]);
        }
        return args;
    }

    public final Object[] printf(String format, Object... args) {
        out.printf(format, args);
        if (autoFlush) flush();
        else outFlush = autoOutFlush;
        return args;
    }

    public final Object printf(Locale l, String format, Object... args) {
        out.printf(l, format, args);
        if (autoFlush) flush();
        else outFlush = autoOutFlush;
        return args;
    }

    public final void println() {
        out.println();
        if (autoFlush) flush();
        else outFlush = autoOutFlush;
    }

    public final boolean println(boolean b) {
        out.println(b);
        if (autoFlush) flush();
        else outFlush = autoOutFlush;
        return b;
    }

    public final Object println(boolean b, Object t, Object f) {
        return b ? println(t) : println(f);
    }

    public final char println(char c) {
        out.println(c);
        if (autoFlush) flush();
        else outFlush = autoOutFlush;
        return c;
    }

    public final char[] println(char[] s) {
        out.println(s);
        if (autoFlush) flush();
        else outFlush = autoOutFlush;
        return s;
    }

    public final double println(double d) {
        out.println(d);
        if (autoFlush) flush();
        else outFlush = autoOutFlush;
        return d;
    }

    public final double println(double d, int length) {
        print(d, length);
        println();
        return d;
    }

    public final float println(float f) {
        out.println(f);
        if (autoFlush) flush();
        else outFlush = autoOutFlush;
        return f;
    }

    public final int println(int i) {
        out.println(i);
        if (autoFlush) flush();
        else outFlush = autoOutFlush;
        return i;
    }

    public final long println(long l) {
        out.println(l);
        if (autoFlush) flush();
        else outFlush = autoOutFlush;
        return l;
    }

    public final Object println(Object obj) {
        print(obj);
        println();
        return obj;
    }

    public final String println(String s) {
        out.println(s);
        if (autoFlush) flush();
        else outFlush = autoOutFlush;
        return s;
    }

    public final Object println(Object array, String... parse) {
        print(array, parse);
        println();
        return array;
    }

    public final boolean debug(boolean b) {
        err.print(b);
        if (autoFlush) flush();
        else outFlush = autoOutFlush;
        return b;
    }

    public final Object debug(boolean b, Object t, Object f) {
        return b ? debug(t) : debug(f);
    }

    public final char debug(char c) {
        err.print(c);
        if (autoFlush) flush();
        else outFlush = autoOutFlush;
        return c;
    }

    public final char[] debug(char[] s) {
        err.print(s);
        return s;
    }

    public final double debug(double d) {
        err.print(d);
        if (autoFlush) flush();
        else outFlush = autoOutFlush;
        return d;
    }

    public final double debug(double d, int length) {
        if (d < 0) {
            err.print('-');
            d = -d;
        }
        d += Math.pow(10, -length) / 2;
        err.print((long)d);
        err.print('.');
        d -= (long)d;
        for (int i = 0;i < length;++ i) {
            d *= 10;
            err.print((int)d);
            d -= (int)d;
        }
        if (autoFlush) flush();
        else outFlush = autoOutFlush;
        return d;
    }

    public final float debug(float f) {
        err.print(f);
        if (autoFlush) flush();
        else outFlush = autoOutFlush;
        return f;
    }

    public final int debug(int i) {
        err.print(i);
        if (autoFlush) flush();
        else outFlush = autoOutFlush;
        return i;
    }

    public final long debug(long l) {
        err.print(l);
        if (autoFlush) flush();
        else outFlush = autoOutFlush;
        return l;
    }

    public final Object debug(Object obj) {
        if (obj != null && obj.getClass().isArray()) {
            if (obj instanceof boolean[][]) debug(obj, "\n", " ");
            else if (obj instanceof byte[][]) debug(obj, "\n", " ");
            else if (obj instanceof short[][]) debug(obj, "\n", " ");
            else if (obj instanceof int[][]) debug(obj, "\n", " ");
            else if (obj instanceof long[][]) debug(obj, "\n", " ");
            else if (obj instanceof float[][]) debug(obj, "\n", " ");
            else if (obj instanceof double[][]) debug(obj, "\n", " ");
            else if (obj instanceof char[][]) debug(obj, "\n", " ");
            else if (obj instanceof Object[][]) debug(obj, "\n", " ");
            else debug(obj, " ");
        } else {
            err.print(obj);
            if (autoFlush) flush();
            else outFlush = autoOutFlush;
        }
        return obj;
    }

    public final String debug(String s) {
        err.print(s);
        if (autoFlush) flush();
        else outFlush = autoOutFlush;
        return s;
    }

    public final Object debug(Object array, String... parse) {
        debug(array, 0, parse);
        if (autoFlush) flush();
        else outFlush = autoOutFlush;
        return array;
    }

    private final Object debug(Object array, int check, String... parse) {
        if (check >= parse.length) {
            if (array != null && array.getClass().isArray()) throw new IllegalArgumentException("not equal dimension");
            debug(array);
            return array;
        }
        String str = parse[check];
        if (array instanceof Object[]) {
            Object[] obj = (Object[]) array;
            if (obj.length == 0) return array;
            debug(obj[0], check + 1, parse);
            for (int i = 1;i < obj.length;++ i) {
                debug(str);
                debug(obj[i], check + 1, parse);
            }
            return array;
        }
        if (array instanceof Collection) {
            Iterator<?> iter = ((Collection<?>)array).iterator();
            if (!iter.hasNext()) return array;
            debug(iter.next(), check + 1, parse);
            while(iter.hasNext()) {
                debug(str);
                debug(iter.next(), check + 1, parse);
            }
            return array;
        }
        if (!array.getClass().isArray()) throw new IllegalArgumentException("not equal dimension");
        if (check != parse.length - 1) throw new IllegalArgumentException("not equal dimension");
        if (array instanceof boolean[]) {
            boolean[] obj = (boolean[]) array;
            if (obj.length == 0) return array;
            debug(obj[0]);
            for (int i = 1;i < obj.length;++ i) {
                debug(str);
                debug(obj[i]);
            }
        } else if (array instanceof byte[]) {
            byte[] obj = (byte[]) array;
            if (obj.length == 0) return array;
            debug(obj[0]);
            for (int i = 1;i < obj.length;++ i) {
                debug(str);
                debug(obj[i]);
            }
            return array;
        } else if (array instanceof short[]) {
            short[] obj = (short[]) array;
            if (obj.length == 0) return array;
            debug(obj[0]);
            for (int i = 1;i < obj.length;++ i) {
                debug(str);
                debug(obj[i]);
            }
        } else if (array instanceof int[]) {
            int[] obj = (int[]) array;
            if (obj.length == 0) return array;
            debug(obj[0]);
            for (int i = 1;i < obj.length;++ i) {
                debug(str);
                debug(obj[i]);
            }
        } else if (array instanceof long[]) {
            long[] obj = (long[]) array;
            if (obj.length == 0) return array;
            debug(obj[0]);
            for (int i = 1;i < obj.length;++ i) {
                debug(str);
                debug(obj[i]);
            }
        } else if (array instanceof float[]) {
            float[] obj = (float[]) array;
            if (obj.length == 0) return array;
            debug(obj[0]);
            for (int i = 1;i < obj.length;++ i) {
                debug(str);
                debug(obj[i]);
            }
        } else if (array instanceof double[]) {
            double[] obj = (double[]) array;
            if (obj.length == 0) return array;
            debug(obj[0]);
            for (int i = 1;i < obj.length;++ i) {
                debug(str);
                debug(obj[i]);
            }
        } else if (array instanceof char[]) {
            char[] obj = (char[]) array;
            if (obj.length == 0) return array;
            debug(obj[0]);
            for (int i = 1;i < obj.length;++ i) {
                debug(str);
                debug(obj[i]);
            }
        } else throw new AssertionError();
        return array;
    }

    public final Object[] debug(String parse, Object... args) {
        debug(args[0]);
        for (int i = 1;i < args.length;++ i) {
            debug(parse);
            debug(args[i]);
        }
        return args;
    }

    public final Object[] debugf(String format, Object... args) {
        err.printf(format, args);
        if (autoFlush) flush();
        else outFlush = autoOutFlush;
        return args;
    }

    public final Object debugf(Locale l, String format, Object... args) {
        err.printf(l, format, args);
        if (autoFlush) flush();
        else outFlush = autoOutFlush;
        return args;
    }

    public final void debugln() {
        err.println();
        if (autoFlush) flush();
        else outFlush = autoOutFlush;
    }

    public final boolean debugln(boolean b) {
        err.println(b);
        if (autoFlush) flush();
        else outFlush = autoOutFlush;
        return b;
    }

    public final Object debugln(boolean b, Object t, Object f) {
        return b ? debugln(t) : debugln(f);
    }

    public final char debugln(char c) {
        err.println(c);
        if (autoFlush) flush();
        else outFlush = autoOutFlush;
        return c;
    }

    public final char[] debugln(char[] s) {
        err.println(s);
        if (autoFlush) flush();
        else outFlush = autoOutFlush;
        return s;
    }

    public final double debugln(double d) {
        err.println(d);
        if (autoFlush) flush();
        else outFlush = autoOutFlush;
        return d;
    }

    public final double debugln(double d, int length) {
        debug(d, length);
        debugln();
        return d;
    }

    public final float debugln(float f) {
        err.println(f);
        if (autoFlush) flush();
        else outFlush = autoOutFlush;
        return f;
    }

    public final int debugln(int i) {
        err.println(i);
        if (autoFlush) flush();
        else outFlush = autoOutFlush;
        return i;
    }

    public final long debugln(long l) {
        err.println(l);
        if (autoFlush) flush();
        else outFlush = autoOutFlush;
        return l;
    }

    public final Object debugln(Object obj) {
        debug(obj);
        debugln();
        return obj;
    }

    public final String debugln(String s) {
        err.println(s);
        if (autoFlush) flush();
        else outFlush = autoOutFlush;
        return s;
    }

    public final Object debugln(Object array, String... parse) {
        debug(array, parse);
        debugln();
        return array;
    }

    public final void flush() {
        out.flush();
        err.flush();
        outFlush = false;
    }

    @Override
    public final void close() {
        out.close();
        err.close();
    }
}

class ModInt implements Comparable<ModInt>{
    static final private int MOD = 1_000_000_007;
    static final public ModInt ZERO = new ModInt(0);
    static final public ModInt ONE = new ModInt(1);
    static final public ModInt TWO = new ModInt(2);
    static final public ModInt TEN = new ModInt(10);
    static final public ModInt MINUSONE = new ModInt(-1);

    static final private ModInt[] fact, factInv;
    static{
        int max = 1000000;
        fact = new ModInt[max+1];
        factInv = new ModInt[max+1];
        fact[0] = ONE;
        for(int i=1; i<=max; i++) fact[i] = fact[i-1].mult(i);
        factInv[max] = fact[max].inverse();
        for (int i = max-1;i >= 0;-- i) factInv[i] = factInv[i + 1].mult(i + 1);
    }


    int num;

    public ModInt(int n){
        this.num = n%MOD;
        if(this.num<0) this.num += MOD;
    }

    public int compareTo(ModInt another){
        return Integer.compare(this.num, another.num);
    }
    public boolean equals(Object another){
        if(another instanceof ModInt) return compareTo((ModInt)another)==0;
        else return false;
    }
    public String toString(){
        return Integer.toString(num);
    }

    ModInt add(ModInt m){
        return new ModInt(this.num + m.num);
    }
    ModInt add(int m){
        m %= MOD;
        return new ModInt(this.num + m);
    }
    ModInt adds(ModInt... ms){
        int ret = this.num;
        for(ModInt m:ms){
            ret = (ret + m.num) % MOD;
        }
        return new ModInt(ret);
    }
    ModInt sub(ModInt m){
        return new ModInt(this.num - m.num);
    }
    ModInt sub(int m){
        return this.add(-m);
    }
    ModInt mult(ModInt m){
        long ret = this.num;
        ret = (ret * m.num)%MOD;
        return new ModInt((int) ret);
    }
    ModInt mult(int m){
        long ret = this.num;
        ret = (ret * m) % MOD;
        return new ModInt((int)ret);
    }
    ModInt mults(ModInt... ms){
        long ret = this.num;
        for(ModInt m:ms) ret = (ret * m.num) % MOD;
        return new ModInt((int) ret);
    }
    ModInt power(int exp){
        if(exp<0) return ZERO;
        long a = this.num;
        long ans = 1;
        while(exp>0){
            if(exp%2==1) ans = (ans * a) % MOD;
            a = (a*a)%MOD;
            exp /= 2;
        }
        return new ModInt((int) ans);
    }
    ModInt inverse(){
        return this.power(MOD-2);
    }
    ModInt divide(ModInt m){
        return this.mult(m.inverse());
    }
    ModInt divide(int m){ return this.divide(new ModInt(m)); }
    static ModInt factorial(int i){
        return fact[i];
    }
    static ModInt combination(int n, int r){
        if(n<0 || r<0 || n<r) return ZERO;
        return fact[n].mults(factInv[r], factInv[n-r]);
    }
    static ModInt permutation(int n, int r){
        if(n<0 || r<0 || n<r) return ZERO;
        return fact[n].mults(factInv[n-r]);
    }
}

public class Main {
    static FastIO io = new FastIO();

    public static void main(String[] args) {
        int N = io.nextInt();
        String S = io.next();

        long R=0, G=0, B=0;
        for(int n=0; n<N; n++){
            if(S.charAt(n)=='R') R++;
            else if(S.charAt(n)=='G') G++;
            else B++;
        }
        long ans = R*G*B;
        for(int i=0; i<N; i++) for(int j=i+1; j<N; j++){
            int k = 2*j-i;
            if(k>=N) break;
            int r=0, g=0, b=0;
            if(S.charAt(i)=='R') r++;
            else if(S.charAt(i)=='G') g++;
            else b++;
            if(S.charAt(j)=='R') r++;
            else if(S.charAt(j)=='G') g++;
            else b++;
            if(S.charAt(k)=='R') r++;
            else if(S.charAt(k)=='G') g++;
            else b++;
            if(r==1 && g==1 && b==1) ans--;
        }

        io.println(ans);
        io.flush();
    }
}


Measured memory_bytes: 33792