import java.io.*; import java.util.*; import static java.lang.Math.*; class FastScanner { // {{{ private final InputStream in = System.in; private final byte[] buffer = new byte[1024]; private int ptr = 0; private int buflen = 0; private boolean hasNextByte() { if(ptr < buflen) { return true; } ptr = 0; try { buflen = in.read(buffer); } catch(IOException ex) { ex.printStackTrace(); } if(buflen <= 0) { return false; } return true; } private int readByte() { if(hasNextByte()) { return buffer[ptr++]; } return -1; } private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126; } private void skipUnprintable() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) { ptr++; } } public boolean hasNext() { skipUnprintable(); return hasNextByte(); } public String next() { if(!hasNext()) { throw new NoSuchElementException(); } StringBuilder sb = new StringBuilder(); int b = readByte(); while(isPrintableChar(b)) { sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } public long nextLong() { if(!hasNext()) { throw new NoSuchElementException(); } long n = 0; boolean minus = false; int b = readByte(); if(b == '-') { minus = true; b = readByte(); } if(b < '0' || '9' < b) { throw new NumberFormatException(); } while(true) { if('0' <= b && b <= '9') { n *= 10; n += b - '0'; } else if(b == -1 || !isPrintableChar(b)) { return minus ? -n : n; } else { throw new NumberFormatException(); } b = readByte(); } } public int nextInt() { if(!hasNext()) { throw new NoSuchElementException(); } int n = 0; boolean minus = false; int b = readByte(); if(b == '-') { minus = true; b = readByte(); } if(b < '0' || '9' < b) { throw new NumberFormatException(); } while(true) { if('0' <= b && b <= '9') { n *= 10; n += b - '0'; } else if(b == -1 || !isPrintableChar(b)) { return minus ? -n : n; } else { throw new NumberFormatException(); } b = readByte(); } } } // }}} strictfp class MersenneTwister extends Random { // {{{ MersenneTwister private static final long serialVersionUID = -515082678588212038L; private final static int UPPER_MASK = 0x80000000; private final static int LOWER_MASK = 0x7fffffff; private final static int N = 624; private final static int M = 397; private final static int[] MAGIC = { 0x0, 0x9908b0df }; private transient int[] mt; private transient int mti; public MersenneTwister() { super(0L); setSeed(System.currentTimeMillis()); } public MersenneTwister(long seed) { super(seed); this.setSeed(seed); } public MersenneTwister(int[] buf) { super(0L); setSeed(buf); } private final void setSeed(int seed) { if(mt == null) { mt = new int[N]; } mt[0] = seed; for(mti=1; mti>> 30)) + mti); } } public final synchronized void setSeed(long seed) { setSeed((int)seed); } public final synchronized void setSeed(int[] buf) { int length = buf.length; if(length == 0) { throw new IllegalArgumentException("buf is empty"); } int i = 1, j = 0, k = (N > length ? N : length); setSeed(19971007); for( ; k>0; --k) { mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >>> 30)) * 1664525)) + buf[j] + j; ++i; ++j; if(i >= N) { mt[0] = mt[N-1]; i = 1; } if(j >= length) { j = 0; } } for(k=N-1; k>0; --k) { mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >>> 30)) * 1566083941)) - i; ++i; if(i >= N) { mt[0] = mt[N-1]; i = 1; } } mt[0] = UPPER_MASK; } protected final synchronized int next(int bits) { int y, kk; if(mti >= N) { for(kk=0; kk>> 1) ^ MAGIC[y & 0x1]; } for( ; kk>> 1) ^ MAGIC[y & 0x1]; } y = (mt[N-1] & UPPER_MASK) | (mt[0] & LOWER_MASK); mt[N-1] = mt[M-1] ^ (y >>> 1) ^ MAGIC[y & 0x1]; mti = 0; } y = mt[mti++]; y ^= (y >>> 11); y ^= (y << 7) & 0x9d2c5680; y ^= (y << 15) & 0xefc60000; y ^= (y >>> 18); return (y >>> (32 - bits)); } public int nextInt31() { return nextInt() >>> 1; } public long nextLong63() { return nextLong() >>> 1; } public void shuffle(List list) { int n = list.size(); for(int i=n-1; i>=1; --i) { int k = nextInt31() % (i + 1); if(k == i) { continue; } Collections.swap(list, k, i); } } } // }}} class MyUtil { private MyUtil() {} public static List segmentSieve(long a, long b) { int sqb = (int)sqrt(b); boolean[] isPrimeSmall = new boolean[sqb+1]; Arrays.fill(isPrimeSmall, true); isPrimeSmall[0] = isPrimeSmall[1] = true; boolean[] isPrime = new boolean[(int)(b-a)]; Arrays.fill(isPrime, true); isPrime[0] = a != 1; for(long i=2; i*i res = new ArrayList<>(); for(long i=0; i primes = MyUtil.segmentSieve(LO, HI); mersenne.shuffle(primes); long[] mods = new long[] {primes.get(0), primes.get(1)}, bases = new long[] {mersenne.nextLong63(), mersenne.nextLong63()}; FastScanner sc = new FastScanner(); String s = sc.next(); RollingHash rhs = new RollingHash(s, mods, bases); int n = s.length(); long[][] cache = new long[11][n]; for(int len=1; len<=10; ++len) { for(int start=0; start+len<=n; ++start) { cache[len][start] = rhs.calcHash(start+1, start+len); } } int M = sc.nextInt(); int res = 0; for(int i=0; i