#define mxPatternSize 101
int F[mxPatternSize];
string pattern;
void buildTable()
{
    F[0] = -1;
    int failValue;
    for(int i=1;i<=pattern.size();i++)
    {
        failValue = F[i-1];

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>

//don't forget to memset DP to -1
long long DP[1005][1005];
long long solve(int X,int Y)
{
    if(!X || !Y)
        return 0;
    long long &nw = DP[X][Y];
    if(nw != -1)
        return nw;
    return DP[X][Y] = DP[Y][X] = (X * Y)+solve(X-1,Y-1);

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>

template <class Type>
class LIS
{
private:
    Type *Arr;
    int ArrSize;
    int *Best2ArrIndex;
    int *Pre;
    Type **BestTillNow;
    int BestSZ;

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>

 
long long CDP[10004][100];//First dimension for N Second for R
long long c(int n, int r)
{
    if(n<r)
        return 0;//ERROR
    if (n == 0 || r == 0 || r == n) return 1LL;
    if (r > n-r) r = n-r;
    long long &nw = CDP[n][r];
    if(nw != 0)

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>

#define getBit  (code,i)   (code &  (1 << i))
#define setBit  (code,i)   (code |  (1 << i))
#define resetBit(code,i)   (code & ~(1 << i))
 
#define getBitM  (code,i,j,D2)   (code & (1 << (i*D2 + j)))
#define setBitM  (code,i,j,D2)   (code | (1 << (i*D2 + j)))
#define resetBitM(code,i,j,D2)   (code & ~(1 << (i*D2 + j)))

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>