In this HackerRank Gridland Provinces problem solution, the Kingdom of Gridland contains P provinces. Each province is defined as a 2 x N grid where each cell in the grid represents a city. Every cell in the grid contains a single lowercase character denoting the first character of the city name corresponding to that cell.

From a city with the coordinates (i,j), it is possible to move to any of the following cells in 1 unit of time (provided that the destination cell is within the confines of the grid):

A knight wants to visit all the cities in Gridland. He can start his journey in any city and immediately stops his journey after having visited each city at least once. Moreover, he always plans his journey in such a way that the total time required to complete it is minimum.

After completing his tour of each province, the knight forms a string by concatenating the characters of all the cells in his path. How many distinct strings can he form in each province?

HackerRank Gridland Provinces problem solution


Problem solution in Python.

#!/bin/python3

import os
import sys

PRIME = 1000000007*65535

PMAP = [int((1<<(5*i)) % PRIME) for i in range(1202)]

def chash(s, p = 0):
    for c in s:
        p = ((p<<5) + ord(c)) % PRIME
    return p

def hmap(s):
    ret = [0]
    for c in s:
        ret.append(((ret[-1]<<5)+ord(c)) % PRIME)
    return ret

def hrange(l,i,j,s):
    return (l[j] + ((s-l[i]) * PMAP[j-i])) % PRIME

def count(s1 : str, s2 : str, s1rev, s2rev):
    ret = set()
    n,n2 = len(s1),2*len(s1)
    left_to_top = s2rev + s1
    left_to_bot = s1rev + s2
    right_from_top = s1 + s2rev
    right_from_bot = s2 + s1rev
    mid_even_tb = [ord(s1[i//2]) if ((i%4) in (0,3)) else ord(s2[i//2]) for i in range(n2)]
    mid_odd_tb = [ord(s2[i//2]) if ((i%4) in (0,3)) else ord(s1[i//2]) for i in range(n2)]
    left_to_top,left_to_bot,right_from_top,right_from_bot = map(hmap,(left_to_top,left_to_bot,right_from_top,right_from_bot))
    mid_even_tb = [mid_even_tb[2*j+1] + mid_even_tb[2*j] * PMAP[1] for j in range(n)]
    mid_odd_tb = [mid_odd_tb[2*j+1] + mid_odd_tb[2*j] * PMAP[1] for j in range(n)]
    for left,mids,rights in (left_to_top,(mid_even_tb,mid_odd_tb),(right_from_top,right_from_bot)),(left_to_bot,(mid_odd_tb,mid_even_tb),(right_from_bot,right_from_top)):
        for i in range(0,n+1):
            mid = mids[i&1]
            s = hrange(left,n-i,n+i,0)
            for j in range(i, n):
                ret.add(hrange(rights[j&1],j,n2-j,s))
                s = (s * PMAP[2] + mid[j]) % PRIME
            ret.add(s)
            rights = rights[::-1]
    return ret

def gridlandProvinces(s1, s2):
    s1rev,s2rev = s1[::-1],s2[::-1]
    return len(count(s1, s2, s1rev, s2rev).union(count(s1rev, s2rev, s1, s2)))

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    p = int(input())

    for p_itr in range(p):
        n = int(input())

        s1 = input()

        s2 = input()

        result = gridlandProvinces(s1, s2)

        fptr.write(str(result) + '\n')

    fptr.close()

{"mode":"full","isActive":false}


Problem solution in Java.

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Solution2 {
private final static Scanner scanner = 
new Scanner(System.in);
private final static long mod1 = 2147483607,
 f1 = 107, f2 = 101;
private final static long[] arr1 = new long[10000], 
arr2 = new long[10000]; 
private final static Set<Long> result = new HashSet<>();
public static void main(String[] args) {
for (int i = 0; i < arr1.length; ++i) {
arr1[i] = i > 0 ? arr1[i - 1] * f1 % mod1 : 1;
arr2[i] = i > 0 ? arr2[i - 1] * f2 % mod1 : 1;
}

for (int t = scanner.nextInt(); t > 0; --t) {
result.clear();
scanner.nextInt();
char[] c1 = scanner.next().toCharArray();
char[] c2 = scanner.next().toCharArray();

for (int i = 0; i < c1.length; ++i) {
process(c1, c2, i, false);
process(c2, c1, i, false); 
process(c1, c2, i, true);
process(c2, c1, i, true);
}
reverse(c1);
reverse(c2);
for (int i = 0; i < c1.length; ++i) {
process(c1, c2, i, false);
process(c2, c1, i, false); 
process(c1, c2, i, true);
process(c2, c1, i, true);
}
System.out.println(result.size());
}
}

static void process(char[] s1, char[] s2, int k, boolean b) {
long p1 = 0, p2 = 0, p3 = 0, p4 = 0;
for (int i = 0; i < k; ++i) {
p1 = (p1 + s1[i] * arr1[k - 1 - i]) % mod1;
p1 = (p1 + s2[i] * arr1[k + i]) % mod1;
p3 = (p3 + s1[i] * arr2[k - 1 - i]) % mod1;
p3 = (p3 + s2[i] * arr2[k + i]) % mod1;
}
if (b) {
p1 = (p1 + s2[k] * arr1[k * 2]) % mod1;
p1 = (p1 + s1[k] * arr1[k * 2 + 1]) % mod1;
p3 = (p3 + s2[k] * arr2[k * 2]) % mod1;
p3 = (p3 + s1[k] * arr2[k * 2 + 1]) % mod1;
char[] s = s1; s1 = s2; s2 = s;
++k;
}
for (int i = k; i < s1.length; ++i) {
p2 = (p2 + s1[i] * arr1[s1.length * 2 + k - 1 - i]) % mod1;
p2 = (p2 + s2[i] * arr1[i + k]) % mod1;
p4 = (p4 + s1[i] * arr2[s1.length * 2 + k - 1 - i]) % mod1;
p4 = (p4 + s2[i] * arr2[i + k]) % mod1;
}
result.add(((p1 + p2) % mod1) * mod1 + (p3 + p4) % mod1);

for (int i = k; i < s1.length - 1; i += 2) {
p1 = (p1 + s2[i] * arr1[i * 2]) % mod1;
p1 = (p1 + s1[i] * arr1[i * 2 + 1]) % mod1;
p1 = (p1 + s1[i + 1] * arr1[i * 2 + 2]) % mod1;
p1 = (p1 + s2[i + 1] * arr1[i * 2 + 3]) % mod1;
p2 = (p2 + s2[i] * (mod1 - arr1[i * 2])) % mod1;
p2 = (p2 + s2[i+1] * (mod1 - arr1[i * 2 + 1])) % mod1;
p2 = (p2 + s1[i] * (mod1 - arr1[s1.length * 2 - 1])) % mod1;
p2 = (p2 + s1[i+1] * (mod1 - arr1[s1.length * 2 - 2])) % mod1;
p2 = (p2 * f1 * f1) % mod1;

p3 = (p3 + s2[i] * arr2[i * 2]) % mod1;
p3 = (p3 + s1[i] * arr2[i * 2 + 1]) % mod1;
p3 = (p3 + s1[i + 1] * arr2[i * 2 + 2]) % mod1;
p3 = (p3 + s2[i + 1] * arr2[i * 2 + 3]) % mod1;
p4 = (p4 + s2[i] * (mod1 - arr2[i * 2])) % mod1;
p4 = (p4 + s2[i+1] * (mod1 - arr2[i * 2 + 1])) % mod1;
p4 = (p4 + s1[i] * (mod1 - arr2[s1.length * 2 - 1])) % mod1;
p4 = (p4 + s1[i+1] * (mod1 - arr2[s1.length * 2 - 2])) % mod1;
p4 = (p4 * f2 * f2) % mod1;

result.add(((p1 + p2) % mod1) * mod1 + (p3 + p4) % mod1);
}
}

private static void reverse(char[] str) {
for (int i = str.length / 2 - 1; i >= 0; --i) {
char t = str[i];
str[i] = str[str.length - 1 - i];
str[str.length - 1 - i] = t;
}
}

}

{"mode":"full","isActive":false}


Problem solution in C++.

#include <cmath>
#include <cstdio>
#include <vector>
#include <set>
#include <iostream>
#include <algorithm>
#include <fstream>
#include <functional>
#include <string>
#include <cstring>
#include <cstdint>
using namespace std;

int gNPaths = 0;
const unsigned int kHashSize = 4096*16;
vector< set<unsigned int> > gHashTab;
size_t gN  = 0;
size_t gNx  = 0;

inline void checkThis(const char *knightPath, const unsigned int hashp = 0){
    auto hashx = (hashp)? hashp : std::_Hash_impl::hash(knightPath, gNx, 11); 
    auto hashy = std::_Hash_impl::hash(knightPath+gNx, gNx, 11); 
    auto hash2 = hashx^(hashy<<1); 
    auto hash  = hashx%kHashSize;
    if(gHashTab[hash].size()==0){
        gHashTab[hash].insert(hash2);
        ++gNPaths;
        return;
    }
    if(gHashTab[hash].size()!=0){
        if(gHashTab[hash].count(hash2)) return;
        gHashTab[hash].insert(hash2);
        ++gNPaths;
        return;
    }
}

void zigs(const string aS, const string bS){
    const int n = aS.size();
    string raS = aS;
    reverse(raS.begin(), raS.end());
    string rbS = bS;
    reverse(rbS.begin(), rbS.end());

    if(n<3) return;
    char a[n+1];
    char b[n+1];
    strcpy(a, aS.c_str());
    strcpy(b, bS.c_str());

    char ra[n+1];
    char rb[n+1];
    strcpy(ra, raS.c_str());
    strcpy(rb, rbS.c_str());

    a[n]='\0';
    b[n]='\0';
    ra[n]='\0';
    rb[n]='\0';

    int kStart = 0;
    for (; kStart < n; ++kStart){
        if(a[kStart]!=a[0] || b[kStart]!=a[0]) break;
    }
    kStart = max(1,kStart);
    int kEnd   = n-1;
    for (; kEnd != 0; --kEnd){
        if(a[kEnd]!=a[n-1] || b[kEnd]!=a[n-1]) break;
    }
    kEnd+=2;
    kEnd = min(n+1,kEnd);
    
    char knightPath[gN+1];
    char revKnightPath[gN+1];
    knightPath[gN]    ='\0';
    revKnightPath[gN] ='\0';

    char frontLoopTop[gN+1];
    memcpy(frontLoopTop, ra, n);
    memcpy(frontLoopTop+n, b, n);
    frontLoopTop[gN]   ='\0';

    char frontLoopBottom[gN+1];
    memcpy(frontLoopBottom, rb, n);
    memcpy(frontLoopBottom+n, a, n);
    frontLoopBottom[gN]   ='\0';

    char tailLoopTop[gN+1];
    memcpy(tailLoopTop, a, n);
    memcpy(tailLoopTop+n, rb, n);
    tailLoopTop[gN]   ='\0';

    char tailLoopBottom[gN+1];
    memcpy(tailLoopBottom, b, n);
    memcpy(tailLoopBottom+n, ra, n);
    tailLoopBottom[gN]   ='\0';
    
    char zigEvenUp[gN+1];
    char zigEvenDown[gN+1];
    bool goingEvenDown = true;
    for (int k = 0; k < n; ++k){
        if(goingEvenDown){
            zigEvenDown[2*k]   = a[k];
            zigEvenDown[2*k+1] = b[k];

            zigEvenUp[2*k]   = b[k];
            zigEvenUp[2*k+1] = a[k];
            goingEvenDown = false;
        }
        else{
            zigEvenDown[2*k]   = b[k];
            zigEvenDown[2*k+1] = a[k];
            zigEvenUp[2*k]   = a[k];
            zigEvenUp[2*k+1] = b[k];
            goingEvenDown = true;
        }
    }
    zigEvenUp[gN]   ='\0';
    zigEvenDown[gN] ='\0';

    for (int k = kStart; k < n; ++k)
    {   
        memcpy(knightPath,    frontLoopTop+n-k,    2*k);
        memcpy(revKnightPath, frontLoopBottom+n-k, 2*k);

        unsigned int hashx    = 0;
        unsigned int revHashx = 0;
        if(2*k>n){
            hashx = std::_Hash_impl::hash(knightPath, gNx, 11);
            revHashx = std::_Hash_impl::hash(revKnightPath, gNx, 11);  
        } 
        for(int i=k+1;i<kEnd;++i){
            bool zigEndsTop = true;
            if(k%2 == 1){ //loop starts at the bottom
                memcpy(knightPath+2*k,    zigEvenDown+2*k, 2*(i-k));
                memcpy(revKnightPath+2*k, zigEvenUp+2*k,   2*(i-k));
            } 
            else{//loop starts at the bottom   
                memcpy(knightPath+2*k,    zigEvenUp+2*k,   2*(i-k)); 
                memcpy(revKnightPath+2*k, zigEvenDown+2*k, 2*(i-k));
            }

            if( i<n ){
                if(i%2 == k%2){
                    memcpy(knightPath+2*i,    tailLoopBottom+i, 2*(n-i)); 
                    memcpy(revKnightPath+2*i, tailLoopTop+i, 2*(n-i)); 
                }
                else{
                    memcpy(knightPath+2*i,    tailLoopTop+i, 2*(n-i)); 
                    memcpy(revKnightPath+2*i, tailLoopBottom+i, 2*(n-i)); 
                }
            }
            checkThis(knightPath, hashx);
            checkThis(revKnightPath, revHashx);
        }
    }
}

void bigLoop(const string a, const string b){
    const int n = a.size();
    
    string knightPath = a + b;
    reverse(knightPath.begin(),knightPath.begin()+n);
    for(int i=0;i<gN;++i){
        rotate(knightPath.begin(), knightPath.begin()+1, knightPath.end());
        checkThis(knightPath.c_str());
    }
}


void paths(const string a, const string b){
    string ra = a;
    reverse(ra.begin(), ra.end());
    string rb = b;
    reverse(rb.begin(), rb.end());

    bigLoop(a, b);
    unsigned int gNPathsAux = gNPaths;

    if(ra == b) return;

    zigs(a, b);

    if(a!=ra || b!=rb){
        bigLoop(ra, rb);
        zigs(ra, rb);
    }
    
}

int main() {

    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    int nTests;
    cin >> nTests;

    for(int i=0;i<nTests;++i){
        gHashTab.clear();
        gHashTab.resize(kHashSize);
        gNPaths = 0;
        int n;
        cin >> n;
        string a,b;
        cin >> a;
        cin >> b;

        gN = a.size()*2;
        gNx = a.size();
        paths(a,b);
        cout << gNPaths << endl;
    }
      
    return 0;
}

{"mode":"full","isActive":false}


Problem solution in C.

#include <stdio.h>
#include <stdlib.h>
#define MOD1 1000000007
#define MOD2 1000000009
#define HASH_SIZE 123455
typedef struct _node{
  int x;
  int y;
  struct _node *next;
} node;
void solve(int i,int j);
void insert(int x,int y);
void freehash();
long long modInverse(long long a,long long mod);
char a[2][601];
int hash_count,N;
long long tr1[1200],tl1[1200],br1[1200],bl1[1200],dr1[1200],dl1[1200],ur1[1200],ul1[1200],mod1[1201],inmod1[1201];
long long tr2[1200],tl2[1200],br2[1200],bl2[1200],dr2[1200],dl2[1200],ur2[1200],ul2[1200],mod2[1201],inmod2[1201];
node *hash[HASH_SIZE]={0};

int main(){
  int T,i,j;
  long long t1,t2;
  scanf("%d",&T);
  while(T--){
    hash_count=0;
    scanf("%d%s%s",&N,&a[0][0],&a[1][0]);
    for(i=0,t1=t2=1;i<N;i++,t1=t1*26%MOD1,t2=t2*26%MOD2)
      if(i){
        tl1[i]=((a[0][i]-'a')*t1+tl1[i-1])%MOD1;
        bl1[i]=((a[1][i]-'a')*t1+bl1[i-1])%MOD1;
        tl2[i]=((a[0][i]-'a')*t2+tl2[i-1])%MOD2;
        bl2[i]=((a[1][i]-'a')*t2+bl2[i-1])%MOD2;
      }
      else{
        tl1[i]=a[0][i]-'a';
        bl1[i]=a[1][i]-'a';
        tl2[i]=a[0][i]-'a';
        bl2[i]=a[1][i]-'a';
      }
    for(i=N-1;i>=0;i--,t1=t1*26%MOD1,t2=t2*26%MOD2){
      tl1[2*N-i-1]=((a[1][i]-'a')*t1+tl1[2*N-i-2])%MOD1;
      bl1[2*N-i-1]=((a[0][i]-'a')*t1+bl1[2*N-i-2])%MOD1;
      tl2[2*N-i-1]=((a[1][i]-'a')*t2+tl2[2*N-i-2])%MOD2;
      bl2[2*N-i-1]=((a[0][i]-'a')*t2+bl2[2*N-i-2])%MOD2;
    }
    for(i=N-1,t1=t2=1;i>=0;i--,t1=t1*26%MOD1,t2=t2*26%MOD2)
      if(i!=N-1){
        tr1[N-i-1]=((a[0][i]-'a')*t1+tr1[N-i-2])%MOD1;
        br1[N-i-1]=((a[1][i]-'a')*t1+br1[N-i-2])%MOD1;
        tr2[N-i-1]=((a[0][i]-'a')*t2+tr2[N-i-2])%MOD2;
        br2[N-i-1]=((a[1][i]-'a')*t2+br2[N-i-2])%MOD2;
      }
      else{
        tr1[N-i-1]=a[0][i]-'a';
        br1[N-i-1]=a[1][i]-'a';
        tr2[N-i-1]=a[0][i]-'a';
        br2[N-i-1]=a[1][i]-'a';
      }
    for(i=0;i<N;i++,t1=t1*26%MOD1,t2=t2*26%MOD2){
      tr1[i+N]=((a[1][i]-'a')*t1+tr1[i+N-1])%MOD1;
      br1[i+N]=((a[0][i]-'a')*t1+br1[i+N-1])%MOD1;
      tr2[i+N]=((a[1][i]-'a')*t2+tr2[i+N-1])%MOD2;
      br2[i+N]=((a[0][i]-'a')*t2+br2[i+N-1])%MOD2;
    }
    for(i=0,t1=t2=1;i<N;i++){
      if(i%2){
        ul1[2*i]=((a[0][i]-'a')*t1+ul1[2*i-1])%MOD1;
        dl1[2*i]=((a[1][i]-'a')*t1+dl1[2*i-1])%MOD1;
        ul2[2*i]=((a[0][i]-'a')*t2+ul2[2*i-1])%MOD2;
        dl2[2*i]=((a[1][i]-'a')*t2+dl2[2*i-1])%MOD2;
      }
      else
        if(!i){
          ul1[2*i]=a[1][i]-'a';
          dl1[2*i]=a[0][i]-'a';
          ul2[2*i]=a[1][i]-'a';
          dl2[2*i]=a[0][i]-'a';
        }
        else{
          ul1[2*i]=((a[1][i]-'a')*t1+ul1[2*i-1])%MOD1;
          dl1[2*i]=((a[0][i]-'a')*t1+dl1[2*i-1])%MOD1;
          ul2[2*i]=((a[1][i]-'a')*t2+ul2[2*i-1])%MOD2;
          dl2[2*i]=((a[0][i]-'a')*t2+dl2[2*i-1])%MOD2;
        }
      t1=t1*26%MOD1;
      t2=t2*26%MOD2;
      if(i%2){
        ul1[2*i+1]=((a[1][i]-'a')*t1+ul1[2*i])%MOD1;
        dl1[2*i+1]=((a[0][i]-'a')*t1+dl1[2*i])%MOD1;
        ul2[2*i+1]=((a[1][i]-'a')*t2+ul2[2*i])%MOD2;
        dl2[2*i+1]=((a[0][i]-'a')*t2+dl2[2*i])%MOD2;
      }
      else{
        ul1[2*i+1]=((a[0][i]-'a')*t1+ul1[2*i])%MOD1;
        dl1[2*i+1]=((a[1][i]-'a')*t1+dl1[2*i])%MOD1;
        ul2[2*i+1]=((a[0][i]-'a')*t2+ul2[2*i])%MOD2;
        dl2[2*i+1]=((a[1][i]-'a')*t2+dl2[2*i])%MOD2;
      }
      t1=t1*26%MOD1;
      t2=t2*26%MOD2;
    }
    for(i=N-1,t1=t2=1;i>=0;i--)
      if(i==N-1){
        ur1[2*(N-1-i)]=a[1][i]-'a';
        dr1[2*(N-1-i)]=a[0][i]-'a';
        ur2[2*(N-1-i)]=a[1][i]-'a';
        dr2[2*(N-1-i)]=a[0][i]-'a';
        t1=t1*26%MOD1;
        t2=t2*26%MOD2;
        ur1[2*(N-1-i)+1]=((a[0][i]-'a')*t1+ur1[2*(N-1-i)])%MOD1;
        dr1[2*(N-1-i)+1]=((a[1][i]-'a')*t1+dr1[2*(N-1-i)])%MOD1;
        ur2[2*(N-1-i)+1]=((a[0][i]-'a')*t2+ur2[2*(N-1-i)])%MOD2;
        dr2[2*(N-1-i)+1]=((a[1][i]-'a')*t2+dr2[2*(N-1-i)])%MOD2;
        t1=t1*26%MOD1;
        t2=t2*26%MOD2;
      }
      else{
        if((N-i)%2==0){
          ur1[2*(N-1-i)]=((a[0][i]-'a')*t1+ur1[2*(N-1-i)-1])%MOD1;
          dr1[2*(N-1-i)]=((a[1][i]-'a')*t1+dr1[2*(N-1-i)-1])%MOD1;
          ur2[2*(N-1-i)]=((a[0][i]-'a')*t2+ur2[2*(N-1-i)-1])%MOD2;
          dr2[2*(N-1-i)]=((a[1][i]-'a')*t2+dr2[2*(N-1-i)-1])%MOD2;
        }
        else{
          ur1[2*(N-1-i)]=((a[1][i]-'a')*t1+ur1[2*(N-1-i)-1])%MOD1;
          dr1[2*(N-1-i)]=((a[0][i]-'a')*t1+dr1[2*(N-1-i)-1])%MOD1;
          ur2[2*(N-1-i)]=((a[1][i]-'a')*t2+ur2[2*(N-1-i)-1])%MOD2;
          dr2[2*(N-1-i)]=((a[0][i]-'a')*t2+dr2[2*(N-1-i)-1])%MOD2;
        }
        t1=t1*26%MOD1;
        t2=t2*26%MOD2;
        if((N-i)%2==0){
          ur1[2*(N-1-i)+1]=((a[1][i]-'a')*t1+ur1[2*(N-1-i)])%MOD1;
          dr1[2*(N-1-i)+1]=((a[0][i]-'a')*t1+dr1[2*(N-1-i)])%MOD1;
          ur2[2*(N-1-i)+1]=((a[1][i]-'a')*t2+ur2[2*(N-1-i)])%MOD2;
          dr2[2*(N-1-i)+1]=((a[0][i]-'a')*t2+dr2[2*(N-1-i)])%MOD2;
        }
        else{
          ur1[2*(N-1-i)+1]=((a[0][i]-'a')*t1+ur1[2*(N-1-i)])%MOD1;
          dr1[2*(N-1-i)+1]=((a[1][i]-'a')*t1+dr1[2*(N-1-i)])%MOD1;
          ur2[2*(N-1-i)+1]=((a[0][i]-'a')*t2+ur2[2*(N-1-i)])%MOD2;
          dr2[2*(N-1-i)+1]=((a[1][i]-'a')*t2+dr2[2*(N-1-i)])%MOD2;
        }
        t1=t1*26%MOD1;
        t2=t2*26%MOD2;
      }
    for(i=0;i<=2*N;i++)
      if(i){
        mod1[i]=mod1[i-1]*26%MOD1;
        inmod1[i]=modInverse(mod1[i],MOD1);
        mod2[i]=mod2[i-1]*26%MOD2;
        inmod2[i]=modInverse(mod2[i],MOD2);
      }
      else
        mod1[i]=inmod1[i]=mod2[i]=inmod2[i]=1;
    for(i=0;i<=N;i++)
      for(j=i;j<=N;j++)
        solve(i,j);
    printf("%d\n",hash_count);
    freehash();
  }
  return 0;
}
void solve(int i,int j){
  long long t1,t2,t3,t4,t5,t6,t7,t8,t9;
  long long tt1,tt2,tt3,tt4,tt5,tt6,tt7,tt8,tt9;
  t1=tr1[N+i-1];
  t2=br1[N+i-1];
  if(i!=N){
    t1=(t1-tr1[N-i-1]+MOD1)%MOD1;
    t2=(t2-br1[N-i-1]+MOD1)%MOD1;
  }
  t1=t1*inmod1[N-i]%MOD1;
  t2=t2*inmod1[N-i]%MOD1;
  t3=tl1[2*N-j-1];
  t4=bl1[2*N-j-1];
  if(j){
    t3=(t3-tl1[j-1]+MOD1)%MOD1;
    t4=(t4-bl1[j-1]+MOD1)%MOD1;
  }
  t3=t3*inmod1[j]%MOD1;
  t4=t4*inmod1[j]%MOD1;
  if(!j)
    t5=t6=0;
  else{
    t5=ul1[2*j-1];
    t6=dl1[2*j-1];
    if(i){
      t5=(t5-ul1[2*i-1]+MOD1)%MOD1;
      t6=(t6-dl1[2*i-1]+MOD1)%MOD1;
    }
  }
  if(i==N)
    t7=t8=0;
  else{
    t7=ur1[2*(N-i)-1];
    t8=dr1[2*(N-i)-1];
    if(j!=N){
      t7=(t7-ur1[2*(N-j)-1]+MOD1)%MOD1;
      t8=(t8-dr1[2*(N-j)-1]+MOD1)%MOD1;
    }
  }
  tt1=tr2[N+i-1];
  tt2=br2[N+i-1];
  if(i!=N){
    tt1=(tt1-tr2[N-i-1]+MOD2)%MOD2;
    tt2=(tt2-br2[N-i-1]+MOD2)%MOD2;
  }
  tt1=tt1*inmod2[N-i]%MOD2;
  tt2=tt2*inmod2[N-i]%MOD2;
  tt3=tl2[2*N-j-1];
  tt4=bl2[2*N-j-1];
  if(j){
    tt3=(tt3-tl2[j-1]+MOD2)%MOD2;
    tt4=(tt4-bl2[j-1]+MOD2)%MOD2;
  }
  tt3=tt3*inmod2[j]%MOD2;
  tt4=tt4*inmod2[j]%MOD2;
  if(!j)
    tt5=tt6=0;
  else{
    tt5=ul2[2*j-1];
    tt6=dl2[2*j-1];
    if(i){
      tt5=(tt5-ul2[2*i-1]+MOD2)%MOD2;
      tt6=(tt6-dl2[2*i-1]+MOD2)%MOD2;
    }
  }
  if(i==N)
    tt7=tt8=0;
  else{
    tt7=ur2[2*(N-i)-1];
    tt8=dr2[2*(N-i)-1];
    if(j!=N){
      tt7=(tt7-ur2[2*(N-j)-1]+MOD2)%MOD2;
      tt8=(tt8-dr2[2*(N-j)-1]+MOD2)%MOD2;
    }
  }
  t9=t1;
  if(i%2)
    t9+=t6;
  else
    t9+=t5;
  if((j-i)%2)
    t9+=t3*mod1[j*2]%MOD1;
  else
    t9+=t4*mod1[j*2]%MOD1;
  t9%=MOD1;
  tt9=tt1;
  if(i%2)
    tt9+=tt6;
  else
    tt9+=tt5;
  if((j-i)%2)
    tt9+=tt3*mod2[j*2]%MOD2;
  else
    tt9+=tt4*mod2[j*2]%MOD2;
  tt9%=MOD2;
  insert(t9,tt9);
  t9=t2;
  if(i%2)
    t9+=t5;
  else
    t9+=t6;
  if((j-i)%2)
    t9+=t4*mod1[j*2]%MOD1;
  else
    t9+=t3*mod1[j*2]%MOD1;
  t9%=MOD1;
  tt9=tt2;
  if(i%2)
    tt9+=tt5;
  else
    tt9+=tt6;
  if((j-i)%2)
    tt9+=tt4*mod2[j*2]%MOD2;
  else
    tt9+=tt3*mod2[j*2]%MOD2;
  tt9%=MOD2;
  insert(t9,tt9);
  t9=t3;
  if((N-j)%2)
    t9+=t8;
  else
    t9+=t7;
  if((j-i)%2)
    t9+=t1*mod1[(N-i)*2]%MOD1;
  else
    t9+=t2*mod1[(N-i)*2]%MOD1;
  t9%=MOD1;
  tt9=tt3;
  if((N-j)%2)
    tt9+=tt8;
  else
    tt9+=tt7;
  if((j-i)%2)
    tt9+=tt1*mod2[(N-i)*2]%MOD2;
  else
    tt9+=tt2*mod2[(N-i)*2]%MOD2;
  tt9%=MOD2;
  insert(t9,tt9);
  t9=t4;
  if((N-j)%2)
    t9+=t7;
  else
    t9+=t8;
  if((j-i)%2)
    t9+=t2*mod1[(N-i)*2]%MOD1;
  else
    t9+=t1*mod1[(N-i)*2]%MOD1;
  t9%=MOD1;
  tt9=tt4;
  if((N-j)%2)
    tt9+=tt7;
  else
    tt9+=tt8;
  if((j-i)%2)
    tt9+=tt2*mod2[(N-i)*2]%MOD2;
  else
    tt9+=tt1*mod2[(N-i)*2]%MOD2;
  tt9%=MOD2;
  insert(t9,tt9);
  return;
}
void insert(int x,int y){
  int bucket=(x+y)%HASH_SIZE;
  node *t=hash[bucket];
  while(t){
    if(t->x==x && t->y==y)
      return;
    t=t->next;
  }
  t=(node*)malloc(sizeof(node));
  t->x=x;
  t->y=y;
  t->next=hash[bucket];
  hash[bucket]=t;
  hash_count++;
  return;
}
void freehash(){
  int i;
  node *t,*p;
  for(i=0;i<HASH_SIZE;i++){
    t=hash[i];
    while(t){
      p=t->next;
      free(t);
      t=p;
    }
    hash[i]=NULL;
  }
  return;
}
long long modInverse(long long a,long long mod){
    long long b0 = mod, t, q;
    long long x0 = 0, x1 = 1;
    while (a > 1) {
        q = a / mod;
        t = mod; mod = a % mod; a = t;
        t = x0; x0 = x1 - q * x0; x1 = t;
    }
    if (x1 < 0) x1 += b0;
    return x1;
}

{"mode":"full","isActive":false}