ssanin82

def find_primes(n):
    ans = list()
    sieve = [1] * n
    for i in xrange(2, n):
        if sieve[i]:
            ans.append(i)
            for j in xrange(i + i, n, i):
                sieve[j] = 0
    return ans

ssanin82

import random


def is_prime(n, k=5):
    if n < 6:
        return [False, False, True, True, False, True][n]
    elif n & 1 == 0:
        return False
    else:
        s, d = 0, n - 1

ssanin82

def is_prime(n):
    if n <= 3:
        return n >= 2
    if n % 2 == 0 or n % 3 == 0:
        return False
    for i in range(5, int(n ** 0.5) + 1, 6):
        if n % i == 0 or n % (i + 2) == 0:
            return False
    return True

ssanin82

def GCD(a,b):
	a = abs(a)
	b = abs(b)
        while a:
                a, b = b%a, a
        return b

ssanin82

from collections import defaultdict

def prime_factors(n):
    if n < 2:
        return None
    d = defaultdict(lambda: 0)
    i = 2
    while i <= n:
        if n % i == 0:
            d[i] += 1

ssanin82

public class Combinations {
    int n;
    int k;
    int[] current;
    boolean init;

    public Combinations(int n, int k) {
        this.n = n;
        this.k = k;
        this.current = new int[k];

ssanin82

typedef long long ULONG;
typedef long long LONG;

inline LONG modinv(LONG a, LONG b) {
    LONG b0 = b, t, q;
    LONG x0 = 0, x1 = 1;
    if (b == 1) {
        return 1;
    }
    while (a > 1) {

ssanin82

typedef unsigned long long ULONG;

ULONG powm(ULONG a, ULONG n, ULONG mod) {
    ULONG r = 1;
    while (n) {
        if (n & 1) {
            r = (r * 1ll * a) % mod;
        }
        a = (a * 1ll * a) % mod;
        n >>= 1;

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);

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) {