Write an API that generates fancy sequences using the append, addAll, and multAll operations.

Implement the Fancy class:


	Fancy() Initializes the object with an empty sequence.
	void append(val) Appends an integer val to the end of the sequence.
	void addAll(inc) Increments all existing values in the sequence by an integer inc.
	void multAll(m) Multiplies all existing values in the sequence by an integer m.
	int getIndex(idx) Gets the current value at index idx (0-indexed) of the sequence modulo 109 + 7. If the index is greater or equal than the length of the sequence, return -1.


&nbsp;
Example 1:

Input
["Fancy", "append", "addAll", "append", "multAll", "getIndex", "addAll", "append", "multAll", "getIndex", "getIndex", "getIndex"]
[[], [2], [3], [7], [2], [0], [3], [10], [2], [0], [1], [2]]
Output
[null, null, null, null, null, 10, null, null, null, 26, 34, 20]

Explanation
Fancy fancy = new Fancy();
fancy.append(2);   // fancy sequence: [2]
fancy.addAll(3);   // fancy sequence: [2+3] -&gt; [5]
fancy.append(7);   // fancy sequence: [5, 7]
fancy.multAll(2);  // fancy sequence: [5*2, 7*2] -&gt; [10, 14]
fancy.getIndex(0); // return 10
fancy.addAll(3);   // fancy sequence: [10+3, 14+3] -&gt; [13, 17]
fancy.append(10);  // fancy sequence: [13, 17, 10]
fancy.multAll(2);  // fancy sequence: [13*2, 17*2, 10*2] -&gt; [26, 34, 20]
fancy.getIndex(0); // return 26
fancy.getIndex(1); // return 34
fancy.getIndex(2); // return 20


&nbsp;
Constraints:


	1 &lt;= val, inc, m &lt;= 100
	0 &lt;= idx &lt;= 105
	At most 105 calls total will be made to append, addAll, multAll, and getIndex.


def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    return x % m

mod = 1000000007

class Fancy(object):

    def __init__(self):
        self.seq = []
        self.addC = 0
        self.mulC = 1
        
    def append(self, val):
        """
        :type val: int
        :rtype: None
        """
        self.seq.append([val, self.mulC, self.addC])
        

    def addAll(self, inc):
        """
        :type inc: int
        :rtype: None
        """
        self.addC = (self.addC%mod + inc%mod)%mod

    def multAll(self, m):
        """
        :type m: int
        :rtype: None
        """
        self.mulC = (self.mulC%mod * m%mod)%mod
        self.addC = (self.addC%mod * m%mod)%mod
        

    def getIndex(self, idx):
        """
        :type idx: int
        :rtype: int
        """
        if(idx >= len(self.seq)):
            return -1
        
        mulCo = self.seq[idx][1]
        addCo = self.seq[idx][2]
        val = self.seq[idx][0]
        
        inv = modinv(mulCo, mod)
        a = (self.mulC%mod * inv%mod)%mod
        val = (val%mod * a%mod)%mod
        b = (addCo%mod * a%mod)%mod
        val = (val%mod - b%mod)%mod
        val = (val%mod + self.addC%mod)%mod
        
        return val
class Fancy {
    private ArrayList<Long> lst;
    private ArrayList<Long> add;
    private ArrayList<Long> mult;
    private final long MOD = 1000000007;

    public Fancy() {
        lst = new ArrayList<>();
        add = new ArrayList<>();
        mult = new ArrayList<>();
        add.add(0L);
        mult.add(1L);
    }

    public void append(int val) {
        lst.add((long) val);
        int l = add.size();
        add.add(add.get(l - 1));
        mult.add(mult.get(l - 1));
    }

    public void addAll(int inc) {
       int l = add.size();
       add.set(l - 1, add.get(l - 1) + inc);
    }

    public void multAll(int m) {
        int l = add.size();
        add.set(l - 1, (add.get(l - 1) * m) % MOD);
        mult.set(l - 1, (mult.get(l - 1) * m) % MOD);
    }

    public int getIndex(int idx) {
        if (idx >= lst.size()) return -1;

        int l = add.size();
        long m = (mult.get(l - 1) * inverse(mult.get(idx))) % MOD;
        long a = (add.get(l - 1) - (add.get(idx) * m) % MOD + MOD) % MOD;
        return (int) (((lst.get(idx) * m) % MOD + a) % MOD);
    }

    long inverse(long a) {
        return pow(a, MOD - 2);
    }

    long pow(long a, long n) {
        if (n == 0) return 1;
        if (n % 2 == 0) {
            long t = pow(a, n / 2);
            return (t * t) % MOD;
        } else {
            return (pow(a, n - 1) * a) % MOD;
        }
    }
}
int mod97 = 1000000007;
/**
Calculates multiplicative inverse
*/
unsigned long modPow(unsigned long x, int y) {
        unsigned long tot = 1, p = x;
        for (; y; y >>= 1) {
            if (y & 1)
                tot = (tot * p) % mod97;
            p = (p * p) % mod97;
        }
        return tot;
    }
class Fancy {
public:
    unsigned long seq[100001];
    unsigned int length = 0;
    unsigned long increment = 0;
    unsigned long mult = 1;
    Fancy() {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
    }
    
    void append(int val) {
        seq[length++] = (((mod97 + val - increment)%mod97) * modPow(mult, mod97-2))%mod97;
    }
    void addAll(int inc) {
        increment = (increment+ inc%mod97)%mod97;
    }
    
    void multAll(int m) {
        mult = (mult* m%mod97)%mod97;
        increment = (increment* m%mod97)%mod97;
    }
    
    int getIndex(int idx) {
        
        if (idx >= length){
            return -1;
        }else{
            return ((seq[idx] * mult)%mod97+increment)%mod97;
        }
    }
};
var Fancy = function() {
    this.sequence = [];
    this.appliedOps = [];
    this.ops = [];
    this.modulo = Math.pow(10, 9) + 7;
};

/**
 * @param {number} val
 * @return {void}
 */
Fancy.prototype.append = function(val) {
    this.sequence.push(val);
    this.appliedOps.push(this.ops.length);
};

/**
 * @param {number} inc
 * @return {void}
 */
Fancy.prototype.addAll = function(inc) {
    this.ops.push(['add', inc]);
};

/**
 * @param {number} m
 * @return {void}
 */
Fancy.prototype.multAll = function(m) {
    this.ops.push(['mult', m]);
};

/**
 * @param {number} idx
 * @return {number}
 */
Fancy.prototype.getIndex = function(idx) {
    if (idx >= this.sequence.length) {
        return -1;
    }

    while (this.appliedOps[idx] < this.ops.length) {
        const [operation, value] = this.ops[this.appliedOps[idx]];
        this.appliedOps[idx]++;

        if (operation === 'mult') {
            this.sequence[idx] = (this.sequence[idx] * value) % this.modulo;
        }

        if (operation === 'add') {
            this.sequence[idx] = (this.sequence[idx] + value) % this.modulo;
        }
    }

    return this.sequence[idx];
};

/**
 * Your Fancy object will be instantiated and called as such:
 * var obj = new Fancy()
 * obj.append(val)
 * obj.addAll(inc)
 * obj.multAll(m)
 * var param_4 = obj.getIndex(idx)
 */
Fancy Sequence