ssanin82

def get_lis(d):
    p = [0 for x in xrange (len (d))]
    m = [0 for x in xrange (len (d) + 1)]
    l = 0
    for i in xrange (len(d)):
        lo = 1
        hi = l
        while lo <= hi:
            mid = (lo + hi) / 2
            if d[m [mid]] < d[i]:

ssanin82

def ifactors(n):
    if n <= 0 :
        return
    yield 1
    i = 2
    while i * i < n:
        if n % i == 0:
            yield i
            yield n / i
        i += 1

ssanin82

def extended_gcd(aa, bb):
    lastremainder, remainder = abs(aa), abs(bb)
    x, lastx, y, lasty = 0, 1, 1, 0
    while remainder:
        lastremainder, (quotient, remainder) = remainder, divmod(lastremainder, remainder)
        x, lastx = lastx - quotient * x, x
        y, lasty = lasty - quotient * y, y
    return lastremainder, lastx * (-1 if aa < 0 else 1), lasty * (-1 if bb < 0 else 1)

ssanin82

def fastmodpow(a, b, x):
    poww = res = 1
    while b:
        if b & 1:
            pw, i = a, 1
            while i < poww:
                pw *= pw
                pw %= x
                i *= 2
            res *= pw

ssanin82

def modinv(a, m):
    orgm = m
    x, lastx, y, lasty = 0, 1, 1, 0
    while m:
        a, (quotient, m) = m, divmod(a, m)
        x, lastx = lastx - quotient * x, x
        y, lasty = lasty - quotient * y, y
    if a != 1:
        raise ValueError
    return lastx % orgm

ssanin82

inline int nFirstDigitsOfPower(int a, int b, int n) {
    double x = b * log10(a);
    double y = floor(pow(10, x - floor(x) + n - 1));
    return int(y);
}

ssanin82

#include <iostream>
#include <vector>

using namespace std;

class Combinations {
    int n;
    int k;
    vector<int> current;
    bool init;

ssanin82

inline long long fastmodpow(long long a, long long b, long long x) {
    if (!x || !a) {
        return 0;
    }
    
    if (1 == a) {
        return 1;
    }
    
    a %= x;

ssanin82

#include <iostream>

using namespace std;

class PascalTriangle {
    long long **ck;
    int size;
    int mod;
public:
    PascalTriangle(int size, int mod = 0): size(size), mod(mod) {

ssanin82

typedef long long ULONG;

inline ULONG fastmodpow(ULONG a, ULONG b, ULONG x) {
    ULONG res;
    if (!b) {
        res = 1;
    } else if (1 == b) {
        res = a;
    } else {
        res = fastmodpow(a, b / 2, x);