Problem: Genos and Saitama went shopping for Christmas trees. However, a different type of tree caught their attention, the exalted Power Tree. 

A Power Tree starts out as a single root vertex indexed 1. A Power Tree grows through a magical phenomenon known as an update. In an update, a single vertex is added to the tree as a child of some other vertex.

Every vertex in the tree (the root and all the added vertices) has some value vi associated with it. The power of a vertex is defined as the strength of the multiset composed of the value associated with this vertex (vi) and the powers of its direct children. The strength of a multiset is defined as the sum of all elements in the multiset multiplied by the number of elements in it. Or in other words for some multiset S: 

<image>

Saitama knows the updates that will be performed on the tree, so he decided to test Genos by asking him queries about the tree during its growth cycle.

An update is of the form 1 p v, and adds a new vertex with value v as a child of vertex p.

A query is of the form 2 u, and asks for the power of vertex u.

Please help Genos respond to these queries modulo 109 + 7.

Input

The first line of the input contains two space separated integers v1 and q (1 ≤ v1 < 109, 1 ≤ q ≤ 200 000) — the value of vertex 1 and the total number of updates and queries respectively.

The next q lines contain the updates and queries. Each of them has one of the following forms: 

  * 1 pi vi, if these line describes an update. The index of the added vertex is equal to the smallest positive integer not yet used as an index in the tree. It is guaranteed that pi is some already existing vertex and 1 ≤ vi < 109. 
  * 2 ui, if these line describes a query. It is guaranteed ui will exist in the tree. 



It is guaranteed that the input will contain at least one query.

Output

For each query, print out the power of the given vertex modulo 109 + 7.

Examples

Input

2 5
1 1 3
1 2 5
1 3 7
1 4 11
2 1


Output

344


Input

5 5
1 1 4
1 2 3
2 2
1 2 7
2 1


Output

14
94

Note

For the first sample case, after all the updates the graph will have vertices labelled in the following manner: 1 — 2 — 3 — 4 — 5

These vertices will have corresponding values: 2 — 3 — 5 — 7 — 11

And corresponding powers: 344 — 170 — 82 — 36 — 11

Solution (in JAVA):

Solution:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class P607D {
    private static final long M = 1000000007L;

    private static final Map<Long, Long> multInverse = new HashMap<>();

    private static long multInverse(long a) {
        Long result = multInverse.get(a);
        if (result != null) {
            return result;
        }

        long i = a;
        long j = M;
        long x0 = 1;
        long x1 = 0;
        long y0 = 0;
        long y1 = 1;
        long tmp;
        while (j != 0) {
            long q = i / j;
            tmp = i % j;
            i = j;
            j = tmp;

            tmp = x0 - q*x1;
            x0 = x1;
            x1 = tmp;

            tmp = y0 - q*y1;
            y0 = y1;
            y1 = tmp;
        }
        result = Math.floorMod(x0, M);
        multInverse.put(a, result);
        return result;
    }

    private static class Interval {
        public final int start;
        public final int end;
        public Interval(int start, int end) {
            this.start = start;
            this.end = end;
        }

        public boolean intersects(Interval other) {
            return start <= other.end && end >= other.start;
        }

        public boolean covers(Interval other) {
            return start <= other.start && end >= other.end;
        }

        public boolean contains(int point) {
            return start <= point && point <= end;
        }

        public int midpoint() {
            return (start + end) / 2;
        }

        @Override
        public String toString() {
            return new StringBuilder()
                .append("[")
                .append(start)
                .append(", ")
                .append(end)
                .append("]")
                .toString();
        }
    }

    private static class IntervalTree {
        private final Interval interval;
        private final boolean hasChildren;
        private final IntervalTree left;
        private final IntervalTree right;

        private long value;
        private long multiplier;
        private long totalMultiplier;

        public IntervalTree(Interval interval) {
            this.interval = interval;

            hasChildren = (interval.start < interval.end);
            if (hasChildren) {
                final int mid = interval.midpoint();
                left = new IntervalTree(new Interval(interval.start, mid));
                right = new IntervalTree(new Interval(mid+1, interval.end));
            } else {
                left = null;
                right = null;
            }

            value = 0;
            multiplier = 1;
            totalMultiplier = 1;
        }

        private void lazyMultiply(long multiplier) {
            this.multiplier = Math.floorMod(this.multiplier * multiplier, M);
        }

        private long evaluate() {
            if (multiplier != 1) {
                value = Math.floorMod(value * multiplier, M);
                totalMultiplier = Math.floorMod(totalMultiplier * multiplier,
                                                M);
                if (hasChildren) {
                    left.lazyMultiply(multiplier);
                    right.lazyMultiply(multiplier);
                }
                multiplier = 1;
            }
            return value;
        }

        public long add(int point, long value) {
            if (!interval.contains(point)) {
                return 0;
            }

            evaluate();
            final long delta;
            if (hasChildren) {
                delta = (left.add(point, value) + right.add(point, value));
            } else {
                delta = Math.floorMod(totalMultiplier * value, M);
            }
            this.value = Math.floorMod(this.value + delta, M);
            return delta;
        }

        public long multiply(Interval interval, long multiplier) {
            if (!interval.intersects(this.interval)) {
                return 0;
            }

            final long oldValue = evaluate();
            if (interval.covers(this.interval)) {
                lazyMultiply(multiplier);
                evaluate();
            } else {
                value = Math.floorMod(
                    value + left.multiply(interval, multiplier)
                        + right.multiply(interval, multiplier), M);
            }
            return value - oldValue;
        }

        public long sum(Interval interval) {
            if (!interval.intersects(this.interval)) {
                return 0;
            }

            evaluate();
            if (interval.covers(this.interval)) {
                return value;
            } else {
                return Math.floorMod(left.sum(interval) + right.sum(interval),
                                     M);
            }
        }

        public long getTotalMultiplier(int point) {
            if (!interval.contains(point)) {
                return 1;
            }

            evaluate();
            if (hasChildren) {
                return left.getTotalMultiplier(point)
                    * right.getTotalMultiplier(point);
            } else {
                return totalMultiplier;
            }
        }

        @Override
        public String toString() {
            final StringBuilder sb = new StringBuilder();
            sb.append("[");
            if (multiplier != 1) {
                sb.append(multiplier).append("*");
            }
            sb.append(value);
            if (hasChildren) {
                sb.append(" ").append(left).append(" ").append(right);
            }
            sb.append("]");
            return sb.toString();
        }
    }

    private static class IB {
        public final int i;
        public final boolean b;
        public IB(int i, boolean b) {
            this.i = i;
            this.b = b;
        }
    }

    private static List<Interval> getIntervals(List<List<Integer>> childLists) {
        List<Interval> intervals = new ArrayList<>(
            Collections.nCopies(childLists.size(), null));
        Deque<IB> stack = new ArrayDeque<>();
        stack.push(new IB(0, true));
        int n = 0;
        while (!stack.isEmpty()) {
            final IB ib = stack.pop();
            final List<Integer> childList = childLists.get(ib.i);
            if (!childList.isEmpty()) {
                if (ib.b) {
                    stack.push(new IB(ib.i, false));
                    for (int i = childList.size()-1; i>=0; i--) {
                        stack.push(new IB(childList.get(i), true));
                    }
                } else {
                    intervals.set(ib.i, new Interval(
                        intervals.get(childList.get(0)).start, n));
                    n += 1;
                }
            } else {
                intervals.set(ib.i, new Interval(n, n));
                n += 1;
            }
        }
        return intervals;
    }

    private static class Command {
        public final boolean type;
        public final int node;
        public final long value;
        private Command(boolean type, int node, long value) {
            this.type = type;
            this.node = node;
            this.value = value;
        }

        public static Command update(int node, long value) {
            return new Command(true, node, value);
        }

        public static Command query(int node) {
            return new Command(false, node, 0);
        }
    }

    private static List<List<Integer>> computeChildLists(
        List<Command> commands) {
        List<List<Integer>> childLists = new ArrayList<>();
        childLists.add(new ArrayList<Integer>());
        for (Command command : commands) {
            if (command.type) {  // Update
                childLists.get(command.node).add(childLists.size());
                childLists.add(new ArrayList<Integer>());
            }
        }
        return childLists;
    }

    private static List<Long> process(long rootValue, List<Command> commands) {
        final List<Long> results = new ArrayList<>();
        final List<List<Integer>> childLists = computeChildLists(commands);
        final List<Interval> intervals = getIntervals(childLists);
        final IntervalTree tree = new IntervalTree(intervals.get(0));
        final int[] degree = new int[childLists.size()];
        tree.add(intervals.get(0).end, rootValue);
        degree[0] = 1;
        int n = 1;
        for (Command command : commands) {
            if (command.type) {  // Insert
                tree.add(intervals.get(n).end, command.value);
                degree[n] = 1;
                final int pdegree = degree[command.node];
                final long multiplier = Math.floorMod(
                    multInverse(pdegree) * (pdegree+1), M);
                tree.multiply(intervals.get(command.node), multiplier);
                degree[command.node] += 1;
                n += 1;
            } else {  // Query
                final Interval interval = intervals.get(command.node);
                final long multiplier = Math.floorMod(
                    degree[command.node] * multInverse(
                        tree.getTotalMultiplier(interval.end)), M);
                final long result = Math.floorMod(
                    tree.sum(interval) * multiplier, M);
                results.add(result);
            }
        }
        return results;
    }

    public static void main(String[] args) throws IOException {
        final BufferedReader in = new BufferedReader(
            new InputStreamReader(System.in));
        String[] s = in.readLine().split(" ");
        final long rootValue = Long.parseLong(s[0]);
        final int numCommands = Integer.parseInt(s[1]);
        final List<Command> commands = new ArrayList<>(numCommands);
        for (int i = 0; i<numCommands; i++) {
            s = in.readLine().split(" ");
            if ("1".equals(s[0])) {
                commands.add(Command.update(Integer.parseInt(s[1])-1,
                                            Long.parseLong(s[2])));
            } else {
                commands.add(Command.query(Integer.parseInt(s[1])-1));
            }
        }
        for (long r : process(rootValue, commands)) {
            System.out.println(r);
        }
    }
}