import java.lang.*;
import java.math.*;
import java.util.*;

public class BigInt {
  protected int signum=0; 		// neg = -1, 0 = 0, pos = 1
  protected int[] mag;	  		// magnitude in little-endian format
  public final static int MAXN=134217728;	// 2^{27} 
  public final static int ENTRYSIZE=10;		// Bits per entry in mag
  protected final static long P=2013265921;	// The prime 15*2^{27}+1
  protected final static int OMEGA=440564289;	// Root of unity 31^{15} mod P
  protected final static int TWOINV=1006632961;	// 2^{-1} mod P