import java.awt.Point; import java.io.IOException; import java.io.InputStream; import java.io.PrintStream; import java.io.PrintWriter; import java.io.Serializable; import java.util.AbstractList; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Arrays; import java.util.Collection; import java.util.Deque; import java.util.HashSet; import java.util.Iterator; import java.util.Locale; import java.util.NoSuchElementException; import java.util.Queue; import java.util.RandomAccess; import java.util.function.BinaryOperator; import java.util.function.UnaryOperator; public class Main_Short implements Runnable{ /** デバッグ用コードのお供に */ private static boolean DEBUG = false; /** 確保するメモリの大きさ(単位: MB)*/ private static final long MEMORY = 64; private final FastIO io; private static class Edge { int src, dest, weight; Edge(int u, int v, int w) { src = u; dest = v; weight = w; } } private void solve(FastIO io) { /* * author: 31536000 * yukicoder contest 221 C問題 * 考察メモ * 辺の左にある頂点集合×右にある頂点集合だけ、その辺が計算対象になる */ int N = io.nextInt(); ArrayList> graph = new ArrayList<>(N); for (@SuppressWarnings("unused")final int i : IntRange.open(N)) graph.add(new ArrayList()); int[] set = new int[N], node = new int[N]; Edge[] parent = new Edge[N]; Arrays.fill(node, 0); Arrays.fill(set, 1); for (@SuppressWarnings("unused")final int i : IntRange.open(N - 1)) { int u = io.nextInt() - 1, v = io.nextInt() - 1, w = io.nextInt(); graph.get(u).add(new Edge(u, v, w)); graph.get(v).add(new Edge(v, u, w)); } long ans = 0; BreadthFirstSearch bfs = new BreadthFirstSearch(), bfs2 = new BreadthFirstSearch(); bfs.push(0); for (final int i : bfs) { if (graph.get(i).size() == 1) bfs2.push(i); for (final Edge j : graph.get(i)) if (bfs.push(j.dest)) { parent[j.dest] = j; ++ node[i]; } } for (final int i : bfs2) { if (i == 0) continue; ans += (long)parent[i].weight * set[i] * (N - set[i]); set[parent[i].src] += set[i]; if (-- node[parent[i].src] <= 0) bfs2.push(parent[i].src); } io.println(ans * 2); } public static void main(String[] args) { Thread.setDefaultUncaughtExceptionHandler((t, e) -> e.printStackTrace()); new Thread(null, new Main_Short(), "", MEMORY * 1048576).start(); } public Main_Short() { io = new FastIO(); //assert (DEBUG = true) | true; // yukicoderだと-eaが付いてるので正しく動かないことに注意 if (DEBUG) { io.setAutoFlush(true); io.println("debug mode"); } } @Override public void run() { solve(io); io.flush(); } // 以下、ライブラリ /** * 幅優先探索を自動的に行うライブラリです。 * @author 31536000 * * @param 幅優先探索の対象となる型 */ public static class BreadthFirstSearch implements Iterable, Iterator{ CircularArray> queue; HashSet hash; int size; /** * キューを1個用いるBFSを用意します。 */ public BreadthFirstSearch() { this(1); } /** * キューをn個用いるBFSを用意します。 * @param n 使うキューの数 */ public BreadthFirstSearch(int n) { queue = new CircularArray>(n); for (int i = 0;i < n;++ i) queue.set(i, new ArrayDeque()); hash = new HashSet(); size = 0; } /** * キューを1個用いて、最初に調べる場所がtのBFSを作成します。 * @param t 最初に調べる値 */ public BreadthFirstSearch(T t) { this(1, t); } /** * キューをn個用いて、最初に調べる場所がtのBFSを作成します。 * @param n 使うキューの数 * @param t 最初に調べる値 */ public BreadthFirstSearch(int n, T t) { this(n); push(t); } /** * 第n番目のキューに新しくtを調べる対象に追加します。 * @param n 使うキューの場所(0はstackとして処理される) * @param t 調べる値 * @return 既にtを調べたことがあるならfalse、まだ調べてないならtrue */ public boolean push(int n, T t) { if (n < 0 || n > queue.size()) throw new IndexOutOfBoundsException(); if (n == 0) { // stackとして使う Deque que = queue.front(); if (!hash.add(t)) return false; que.addFirst(t); } else { // queueとして使う Deque que = queue.get(n - 1); if (!hash.add(t)) return false; que.addLast(t); } ++ size; return true; } /** * 1番目のキューに新しくtを調べる対象に追加します。 * @param t 調べる値 * @return 既にtを調べたことがあるならfalse、まだ調べてないならtrue */ public boolean push(T t) { if (!hash.add(t)) return false; queue.front().addLast(t); ++ size; return true; } /** * 既にその要素を調べているか返します。 * @param t 調べる値 * @return 既に調べていたらtrue */ public boolean contains(T t) { return hash.contains(t); } /** * BFSを初期化します。 */ public void clear() { for (Deque i : queue) i.clear(); hash.clear(); size = 0; } @Override public Iterator iterator() { return this; } @Override public boolean hasNext() { return size > 0; } @Override public T next() { if (size <= 0) throw new NoSuchElementException(); while (queue.front().isEmpty()) queue.rotateNext(); -- size; return queue.front().pollFirst(); } } /** * 端がもう片側の端と繋がり、循環する固定長配列を提供します。 * @author 31536000 * * @param 配列の型 */ public static class CircularArray extends Array{ private static final long serialVersionUID = 8755553665486205607L; private int first = 0; /** * 長さsizeで、初期の要素が全てnullの配列を作成します。 * @param size 要素数 */ public CircularArray(int size) { super(size); } /** * arrayを固定長配列として扱います。 * @param array 元となる配列 */ public CircularArray(T[] array) { super(array); } /** * index番目の要素を取得します。 * @param index 取得する要素のインデックス * @return index番目の要素 */ private int getIndex(int index) { index -= first; if (index >= size()) index %= size(); else if (index < 0) index = size() + index % size(); return index; } /** * 先頭の要素を上書きします。
* この関数はset(0, value)と同一です。 * @param value 上書きする要素 */ public void setFront(T value) { super.set(first, value); } /** * index番目の要素を上書きします。
* この時、indexは要素数を法とする自然数上に丸められます。 * @param index 上書きする場所 * @param value 上書きする値 */ @Override public T set(int index, T value) { return super.set(getIndex(index), value); } /** * 末尾の要素を上書きします。
* この関数はset(-1, value)と同一です。 * @param value 上書きする要素 */ public void setBack(T value) { super.set(first == 0 ? size() - 1 : first - 1, value); } /** * index番目の要素を取得します。
* この時、indexは要素数を法とする自然数上に丸められます。 * @param index 取得する場所 * @return index番目の要素 */ @Override public T get(int index) { return super.get(getIndex(index)); } /** * 先頭の要素を取得します。
* この関数はget(0)と同一です。 * @return 先頭の要素 */ @Override public T front() { return super.get(first); } /** * 末尾の要素を取得します。
* この関数はget(-1)と同一です。 * @return 末尾の要素 */ @Override public T back() { return super.get(first == 0 ? size() - 1 : first - 1); } /** * 先頭の位置をずらします。
* 例えばrotateが1の時、get(1)で取り出せていた要素は次からget(0)で取り出せるようになります。 * @param rotate ずらす量 */ public void rotate(int rotate) { first = getIndex(rotate); } /** * 先頭の位置を一つ後にずらします。
* この関数はrotate(1)と同一です。 */ public void rotateNext() { if (++first >= size()) first = 0; } /** * 先頭の位置を一つ前にずらします。
* この関数はrotate(-1)と同一です。 */ public void rotatePrevious() { if (--first < 0) first = size() - 1; } private class Iter implements Iterator { private int index; private int count; Iter() { index = first; count = 0; } @Override public boolean hasNext() { return count < size(); } @Override public T next() { T ret = get(index); if (++index >= size()) index = 0; ++ count; return ret; } @Override public void remove() { throw new UnsupportedOperationException(); } } @Override public Iterator iterator() { return new Iter(); } } public static class FastIO { private final InputStream in; private final byte[] buffer = new byte[1024]; private int read = 0; private int length = 0; public final PrintWriter out; public final PrintWriter err; private boolean autoFlush = false; 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 void setAutoFlush(boolean flush) { autoFlush = 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 int readByte() { return hasNextByte() ? buffer[read++] : -1; } private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126; } private static boolean isNumber(int c) { return '0' <= c && c <= '9'; } public boolean hasNext() { while (hasNextByte() && !isPrintableChar(buffer[read])) read++; return hasNextByte(); } public char nextChar() { if (!hasNextByte()) throw new NoSuchElementException(); return (char)readByte(); } public char[][] nextChar(int height) { char[][] ret = new char[height][]; for (int i = 0;i < ret.length;++ i) ret[i] = next().toCharArray(); return ret; } public String next() { if (!hasNext()) throw new NoSuchElementException(); StringBuilder sb = new StringBuilder(); int b; while (isPrintableChar(b = readByte())) sb.appendCodePoint(b); return sb.toString(); } public String nextLine() { StringBuilder sb = new StringBuilder(); int b; while(!isPrintableChar(b = readByte())); do sb.appendCodePoint(b); while(isPrintableChar(b = readByte()) || b == ' '); return sb.toString(); } public long nextLong() { if (!hasNext()) throw new NoSuchElementException(); long n = 0; boolean minus = false; int b = readByte(); if (b == '-') { minus = true; b = readByte(); } if (!isNumber(b)) throw new NumberFormatException(); while (true) { if (isNumber(b)) { n *= 10; n += b - '0'; } else if (b == -1 || !isPrintableChar(b)) return minus ? -n : n; else throw new NumberFormatException(); b = readByte(); } } public int nextInt() { long nl = nextLong(); if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException(); return (int) nl; } public double nextDouble() { return Double.parseDouble(next()); } public int[] nextInt(int width) { int[] ret = new int[width]; for (int i = 0;i < width;++ i) ret[i] = nextInt(); return ret; } public int[] nextInts() { return nextInts(" "); } public 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(ret[i]); return ret; } public long[] nextLong(int width) { long[] ret = new long[width]; for (int i = 0;i < width;++ i) ret[i] = nextLong(); return ret; } public long[] nextLongs() { return nextLongs(" "); } public 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(ret[i]); return ret; } public 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 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 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 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; } public Point nextPoint() { return new Point(nextInt(), nextInt()); } public Point[] nextPoint(int width) { Point[] ret = new Point[width]; for (int i = 0;i < width;++ i) ret[i] = nextPoint(); return ret; } @Override protected void finalize() throws Throwable { try { super.finalize(); } finally { in.close(); out.close(); err.close(); } } public boolean print(boolean b) { out.print(b); if (autoFlush) flush(); return b; } public Object print(boolean b, Object t, Object f) { return b ? print(t) : print(f); } public char print(char c) { out.print(c); if (autoFlush) flush(); return c; } public char[] print(char[] s) { out.print(s); return s; } public double print(double d) { out.print(d); if (autoFlush) flush(); return d; } public 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(); return d; } public float print(float f) { out.print(f); if (autoFlush) flush(); return f; } public int print(int i) { out.print(i); if (autoFlush) flush(); return i; } public long print(long l) { out.print(l); if (autoFlush) flush(); return l; } public Object print(Object obj) { if (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(); } return obj; } public String print(String s) { out.print(s); if (autoFlush) flush(); return s; } public Object print(Object array, String... parse) { print(array, 0, parse); if (autoFlush) flush(); return array; } private Object print(Object array, int check, String... parse) { if (check >= parse.length) { if (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 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 Object[] printf(String format, Object... args) { out.printf(format, args); if (autoFlush) flush(); return args; } public Object printf(Locale l, String format, Object... args) { out.printf(l, format, args); if (autoFlush) flush(); return args; } public void println() { out.println(); if (autoFlush) flush(); } public boolean println(boolean b) { out.println(b); if (autoFlush) flush(); return b; } public Object println(boolean b, Object t, Object f) { return b ? println(t) : println(f); } public char println(char c) { out.println(c); if (autoFlush) flush(); return c; } public char[] println(char[] s) { out.println(s); if (autoFlush) flush(); return s; } public double println(double d) { out.println(d); if (autoFlush) flush(); return d; } public double println(double d, int length) { print(d, length); println(); return d; } public float println(float f) { out.println(f); if (autoFlush) flush(); return f; } public int println(int i) { out.println(i); if (autoFlush) flush(); return i; } public long println(long l) { out.println(l); if (autoFlush) flush(); return l; } public Object println(Object obj) { print(obj); println(); return obj; } public String println(String s) { out.println(s); if (autoFlush) flush(); return s; } public Object println(Object array, String... parse) { print(array, parse); println(); return array; } public void flush() { out.flush(); err.flush(); } } public enum BoundType { CLOSED, OPEN; } public static class IntRange implements Iterable{ protected final int lower; protected final int upper; protected final UnaryOperator func; private final boolean useFastIter; private static class Next implements UnaryOperator { @Override public Integer apply(Integer value) { return value + 1; } } private IntRange(int lower, int upper, UnaryOperator func, boolean useFast) { this.lower = lower; this.upper = upper; this.func = func; this.useFastIter = useFast; } protected IntRange() { this(Integer.MAX_VALUE, Integer.MIN_VALUE, new Next(), true); } protected IntRange(UnaryOperator func) { this(0, 0, func, false); } public static IntRange range(int lower, BoundType lowerType, int upper, BoundType upperType) { if (lower > upper) return new IntRange(); if (lowerType == BoundType.OPEN) ++ lower; if (upperType == BoundType.OPEN) -- upper; return new IntRange(lower, upper, new Next(), true); } public static IntRange range(int lower, BoundType lowerType, int upper, BoundType upperType, UnaryOperator func) { if (lower > upper) return new IntRange(func); if (lowerType == BoundType.OPEN) ++ lower; if (upperType == BoundType.OPEN) -- upper; return new IntRange(lower, upper, func, false); } public static IntRange open(int lower, int upper) { return range(lower, BoundType.OPEN, upper, BoundType.OPEN); } public static IntRange open(int lower, int upper, UnaryOperator func) { return range(lower, BoundType.OPEN, upper, BoundType.OPEN, func); } public static IntRange open(int upper) { return range(0, BoundType.CLOSED, upper, BoundType.OPEN); } public static IntRange open(int upper, UnaryOperator func) { return range(0, BoundType.CLOSED, upper, BoundType.OPEN, func); } public static IntRange openClosed(int lower, int upper) { return range(lower, BoundType.OPEN, upper, BoundType.CLOSED); } public static IntRange openClosed(int lower, int upper, UnaryOperator func) { return range(lower, BoundType.OPEN, upper, BoundType.CLOSED, func); } public static IntRange closedOpen(int lower, int upper) { return range(lower, BoundType.CLOSED, upper, BoundType.OPEN); } public static IntRange closedOpen(int lower, int upper, UnaryOperator func) { return range(lower, BoundType.CLOSED, upper, BoundType.OPEN, func); } public static IntRange closed(int lower, int upper) { return range(lower, BoundType.CLOSED, upper, BoundType.CLOSED); } public static IntRange closed(int lower, int upper, UnaryOperator func) { return range(lower, BoundType.CLOSED, upper, BoundType.CLOSED, func); } public static IntRange closed(int upper) { return range(0, BoundType.CLOSED, upper, BoundType.CLOSED); } public static IntRange closed(int upper, UnaryOperator func) { return range(0, BoundType.CLOSED, upper, BoundType.CLOSED, func); } public static IntRange singleton(int value) { return range(value, BoundType.CLOSED, value, BoundType.CLOSED); } public static IntRange singleton(int value, UnaryOperator func) { return range(value, BoundType.CLOSED, value, BoundType.CLOSED, func); } public boolean contains(int value) { return lower <= value && value <= upper; } private class FastIter implements Iterator { int now; public FastIter() { now = lower; } @Override public final boolean hasNext() { return now <= upper; } @Override public final Integer next() { return now++; } @Override public final void remove() { throw new UnsupportedOperationException(); } } private class Iter implements Iterator { int now; public Iter() { now = lower; } @Override public final boolean hasNext() { return now <= upper; } @Override public final Integer next() { int ret = now; now = func.apply(now); return ret; } @Override public final void remove() { throw new UnsupportedOperationException(); } } public Iterator iterator() { return useFastIter ? new FastIter() : new Iter(); } public int getDistance() { return upper - lower + 1; } public int getClosedLower() { return lower; } public int getOpenLower() { return lower - 1; } public int getClosedUpper() { return upper; } public int getOpenUpper() { return upper + 1; } @Override public String toString() { if (lower > upper) return "()"; return ("[" + lower + ".." + upper + "]"); } } public interface Associative extends BinaryOperator{ public default T hyper(T element, int repeat) { if (repeat < 1) throw new IllegalArgumentException("undefined operation"); T ret = element; -- repeat; for (T mul = element;repeat > 0;repeat >>= 1, mul = apply(mul, mul)) if ((repeat & 1) != 0) ret = apply(ret, mul); return ret; } } public interface Inverse extends BinaryOperator{ public T inverse(T element); } public interface Commutative extends BinaryOperator{ } public interface Unit extends BinaryOperator{ public T unit(); } public interface Group extends Monoid, Inverse{ @Override public default T hyper(T element, int repeat) { T ret = unit(); if (repeat < 0) { repeat = -repeat; for (T mul = element;repeat > 0;repeat >>= 1, mul = apply(mul, mul)) if ((repeat & 1) != 0) ret = apply(ret, mul); return inverse(ret); } for (T mul = element;repeat > 0;repeat >>= 1, mul = apply(mul, mul)) if ((repeat & 1) != 0) ret = apply(ret, mul); return ret; } } public interface Monoid extends Associative, Unit { @Override public default T hyper(T element, int repeat) { if (repeat < 0) throw new IllegalArgumentException("undefined operation"); T ret = unit(); for (T mul = element;repeat > 0;repeat >>= 1, mul = apply(mul, mul)) if ((repeat & 1) != 0) ret = apply(ret, mul); return ret; } } public interface CommutativeMonoid extends Monoid, Commutative { } public interface Abelian extends Group, CommutativeMonoid { } public interface Semiring, M extends Monoid> { public A getAddition(); public M getMultiplication(); } public interface Ring, M extends Monoid> extends Semiring{ } public interface CommutativeRing, M extends CommutativeMonoid> extends Ring{ } public static class ModInteger extends Number implements CommutativeRing, CommutativeMonoid>{ private static final long serialVersionUID = -8595710127161317579L; private final int mod; private int num; private final Addition add; private final Multiplication mul; private class Addition implements Abelian { @Override public ModInteger unit() { return new ModInteger(mod, 0); } @Override public ModInteger inverse(ModInteger element) { return new ModInteger(element, element.mod - element.num); } @Override public ModInteger apply(ModInteger left, ModInteger right) { return new ModInteger(left).addEqual(right); } } private class Multiplication implements Abelian { @Override public ModInteger unit() { return new ModInteger(mod, 1); } @Override public ModInteger apply(ModInteger left, ModInteger right) { return new ModInteger(left).multiplyEqual(right); } @Override public ModInteger inverse(ModInteger element) { return new ModInteger(element, element.inverse(element.num)); } } public ModInteger(int mod) { this.mod = mod; num = 0; add = new Addition(); mul = new Multiplication(); } public ModInteger(int mod, int num) { this.mod = mod; this.num = validNum(num); add = new Addition(); mul = new Multiplication(); } public ModInteger(ModInteger n) { mod = n.mod; num = n.num; add = n.add; mul = n.mul; } private ModInteger(ModInteger n, int num) { mod = n.mod; this.num = num; add = n.add; mul = n.mul; } private int validNum(int n) { n %= mod; if (n < 0) n += mod; return n; } private int validNum(long n) { n %= mod; if (n < 0) n += mod; return (int)n; } protected int inverse(int n) { int m = mod, u = 0, v = 1, t; while(n != 0) { t = m / n; m -= t * n; u -= t * v; if (m != 0) { t = n / m; n -= t * m; v -= t * u; } else { v %= mod; if (v < 0) v += mod; return v; } } u %= mod; if (u < 0) u += mod; return u; } public boolean isPrime(int n) { if ((n & 1) == 0) return false; for (int i = 3, j = 8, k = 9;k <= n;i += 2, k += j += 8) if (n % i == 0) return false; return true; } @Override public int intValue() { return num; } @Override public long longValue() { return num; } @Override public float floatValue() { return num; } @Override public double doubleValue() { return num; } public ModInteger add(int n) { return new ModInteger(this).addEqual(n); } public ModInteger add(long n) { return new ModInteger(this).addEqual(n); } public ModInteger add(ModInteger n) { return new ModInteger(this).addEqual(n); } public ModInteger addEqual(int n) { num = validNum(num + n); return this; } public ModInteger addEqual(long n) { num = validNum(num + n); return this; } public ModInteger addEqual(ModInteger n) { if ((num += n.num) >= mod) num -= mod; return this; } public ModInteger subtract(int n) { return new ModInteger(this).subtractEqual(n); } public ModInteger subtract(long n) { return new ModInteger(this).subtractEqual(n); } public ModInteger subtract(ModInteger n) { return new ModInteger(this).subtractEqual(n); } public ModInteger subtractEqual(int n) { num = validNum(num - n); return this; } public ModInteger subtractEqual(long n) { num = validNum(num - n); return this; } public ModInteger subtractEqual(ModInteger n) { if ((num -= n.num) < 0) num += mod; return this; } public ModInteger multiply(int n) { return new ModInteger(this).multiplyEqual(n); } public ModInteger multiply(long n) { return new ModInteger(this).multiplyEqual(n); } public ModInteger multiply(ModInteger n) { return new ModInteger(this).multiplyEqual(n); } public ModInteger multiplyEqual(int n) { num = (int)((long)num * n % mod); if (num < 0) num += mod; return this; } public ModInteger multiplyEqual(long n) { return multiplyEqual((int) (n % mod)); } public ModInteger multiplyEqual(ModInteger n) { num = (int)((long)num * n.num % mod); return this; } public ModInteger divide(int n) { return new ModInteger(this).divideEqual(n); } public ModInteger divide(long n) { return new ModInteger(this).divideEqual(n); } public ModInteger divide(ModInteger n) { return new ModInteger(this).divideEqual(n); } public ModInteger divideEqual(int n) { num = (int)((long)num * inverse(validNum(n)) % mod); return this; } public ModInteger divideEqual(long n) { return divideEqual((int)(n % mod)); } public ModInteger divideEqual(ModInteger n) { num = (int)((long)num * n.inverse(n.num) % mod); return this; } public ModInteger pow(int n) { return new ModInteger(this).powEqual(n); } public ModInteger pow(long n) { return new ModInteger(this).powEqual(n); } public ModInteger pow(ModInteger n) { return new ModInteger(this).powEqual(n); } public ModInteger powEqual(int n) { long ans = 1, num = this.num; if (n < 0) { n = -n; while (n != 0) { if ((n & 1) != 0) ans = ans * num % mod; n >>>= 1; num = num * num % mod; } this.num = inverse((int)ans); return this; } while (n != 0) { if ((n & 1) != 0) ans = ans * num % mod; n >>>= 1; num = num * num % mod; } this.num = (int)ans; return this; } public ModInteger powEqual(long n) { return powEqual((int)(n % (mod - 1))); } public ModInteger powEqual(ModInteger n) { long num = this.num; this.num = 1; int mul = n.num; while (mul != 0) { if ((mul & 1) != 0) this.num *= num; mul >>>= 1; num *= num; num %= mod; } return this; } public ModInteger equal(int n) { num = validNum(n); return this; } public ModInteger equal(long n) { num = validNum(n); return this; } public ModInteger equal(ModInteger n) { num = n.num; return this; } public int toInt() { return num; } public int getMod() { return mod; } @Override public boolean equals(Object x) { if (x instanceof ModInteger) return ((ModInteger)x).num == num && ((ModInteger)x).mod == mod; return false; } @Override public int hashCode() { return num ^ mod; } @Override public String toString() { return String.valueOf(num); } @Deprecated public String debug() { int min = num, ans = 1; for (int i = 2;i < min;++ i) { int tmp = multiply(i).num; if (min > tmp) { min = tmp; ans = i; } } return min + "/" + ans; } @Override public Addition getAddition() { return add; } @Override public Multiplication getMultiplication() { return mul; } } public static class ModUtility { private final int mod, totient; private int[] fact, inv, invfact; public ModUtility(int mod) { this(mod, 2); } public ModUtility(int mod, int calc) { if (mod <= 0) throw new IllegalArgumentException("illegal mod: " + mod); this.mod = mod; int totient = mod; for (int i = 2;i * i <= mod;++ i) { if (mod % i == 0) { totient = totient / i * (i - 1); while ((mod %= i) % i == 0); } } this.totient = totient; precalc(calc); } public void precalc(int calc) { if (calc < 2) calc = 2; fact = new int[calc]; inv = new int[calc]; invfact = new int[calc]; fact[0] = invfact[0] = fact[1] = invfact[1] = inv[1] = 1; for (int i = 2;i < calc;++ i) { fact[i] = (int)((long)fact[i - 1] * i % mod); inv[i] = (int)(mod - (long)inv[mod % i] * (mod / i) % mod); invfact[i] = (int)((long)invfact[i - 1] * inv[i] % mod); } } public ModInteger create() { return create(0); } public ModInteger create(int n) { return new ModInt(n); } private class ModInt extends ModInteger { private static final long serialVersionUID = -2435281861935422575L; public ModInt(int n) { super(mod, n); } @Override protected int inverse(int n) { return ModUtility.this.inverse(n); } } public int inverse(int n) { try { if (inv.length > n) return inv[n]; int m = mod, u = 0, v = 1, t; while(n != 0) { t = m / n; m -= t * n; u -= t * v; if (m != 0) { t = n / m; n -= t * m; v -= t * u; } else { v %= mod; if (v < 0) v += mod; return v; } } u %= mod; if (u < 0) u += mod; return u; } catch (ArrayIndexOutOfBoundsException e) { throw new IllegalArgumentException(); } } public int factorial(int n) { try { if (fact.length > n) return fact[n]; long ret = fact[fact.length - 1]; for (int i = fact.length;i <= n;++ i) ret = ret * i % mod; return (int)ret; } catch (ArrayIndexOutOfBoundsException e) { throw new IllegalArgumentException(); } } public int permutation(int n, int k) { if (k < 0) throw new IllegalArgumentException(); if (n < k) return 0; if (fact.length > n) return (int)((long)fact[n] * invfact[n - k] % mod); long ret = 1; for (int i = n - k + 1;i <= n;++ i) ret = ret * i % mod; return (int)ret; } public int combination(int n, int k) { if (k < 0) throw new IllegalArgumentException(); if (n < k) return 0; if (fact.length > n) return (int)((long)fact[n] * invfact[k] % mod * invfact[n - k] % mod); long ret = 1; if (n < 2 * k) k = n - k; if (invfact.length > k) ret = invfact[k]; else ret = inverse(factorial(k)); for (int i = n - k + 1;i <= n;++ i) ret = ret * i % mod; return (int)ret; } public int multinomial(int n, int... k) { int sum = 0; for (int i : k) sum += i; long ret = factorial(n); if (fact.length > n) { for (int i : k) { if (i < 0) throw new IllegalArgumentException(); ret = ret * invfact[i] % mod; sum += i; } if (sum > n) return 0; ret = ret * invfact[n - sum] % mod; } else { for (int i : k) { if (i < 0) throw new IllegalArgumentException(); if (invfact.length > i) ret = ret * invfact[i] % mod; else ret = ret * inverse(factorial(i)) % mod; sum += i; } if (sum > n) return 0; if (invfact.length > n - sum) ret = ret * invfact[n - sum] % mod; else ret = ret * inverse(factorial(n - sum)) % mod; } return (int)ret; } public int multichoose(int n, int k) { return combination(mod(n + k - 1), k); } public int catalan(int n) { return divide(combination(mod(2 * n), n), mod(n + 1)); } public int pow(int n, int m) { long ans = 1, num = n; if (m < 0) { m = -m; while (m != 0) { if ((m & 1) != 0) ans = ans * num % mod; m >>>= 1; num = num * num % mod; } return inverse((int)ans); } while (m != 0) { if ((m & 1) != 0) ans = ans * num % mod; m >>>= 1; num = num * num % mod; } return (int)ans; } public int pow(long n, long m) { return pow((int)(n % mod), (int)(m % (mod - 1))); } public int totient() { return totient; } public boolean isPrime() { return totient == mod - 1; } public int mod(int n) { return (n %= mod) < 0 ? n + mod : n; } public int mod(long n) { return (int)((n %= mod) < 0 ? n + mod : n); } public int add(int n, int m) { return mod(n + m); } public int add(long n, long m) { return mod(n + m); } public int subtract(int n, int m) { return mod(n - m); } public int subtract(long n, long m) { return mod(n - m); } public int multiply(int n, int m) { int ans = (int)((long)n * m % mod); return ans < 0 ? ans + mod : ans; } public int multiply(long n, long m) { return multiply(mod(n), mod(m)); } public int divide(int n, int m) { return multiply(n, inverse(mod(m))); } public int divide(long n, long m) { return multiply(n, inverse(mod(m))); } } public static class AbstractArray extends AbstractList implements RandomAccess{ private final Object[] array; public AbstractArray(int size) { array = new Object[size]; } public AbstractArray(T[] array) { this(array.length); System.arraycopy(array, 0, this.array, 0, array.length); } @Override public T set(int index, T element) { T ret = get(index); array[index] = element; return ret; } @Override public T get(int index) { @SuppressWarnings("unchecked") T ret = (T)array[index]; return ret; } public Object[] get() { return array; } public T[] get(T[] array) { if (array.length < this.array.length) { @SuppressWarnings("unchecked") T[] ret = (T[])Arrays.copyOfRange(this.array, 0, this.array.length, array.getClass()); return ret; } System.arraycopy(this.array, 0, array, 0, this.array.length); return array; } @Override public int size() { return array.length; } public int length() { return size(); } @Override public int hashCode() { return Arrays.hashCode(array); } private class Iter implements Iterator { private int index; private Iter() { index = 0; } @Override public boolean hasNext() { return index < array.length; } @Override public T next() { return get(index++); } @Override public void remove() { throw new UnsupportedOperationException(); } } @Override public Iterator iterator() { return new Iter(); } } public static class Array extends AbstractArray implements Serializable{ private static final long serialVersionUID = 2749604433067098063L; public Array(int size) { super(size); } public Array(T[] array) { super(array); } public T front() { return get(0); } public T back() { return get(size() - 1); } } }