You are given regular $n$-gon. Each vertex of the $n$-gon was randomly colored with one of $n$ colors. Your task is to find the number of special subsets of polygon vertices. Each special subset must meet all the requirements:

The subset must contain at least two vertices.
If vertices belonging to the subset are erased from the polygon (note, that the adjacent edges of those vertices will also get erased), the remaining vertices and edges form some continuous paths. None of those paths should contain two vertices of the same color.

Please, calculate the number of described special subsets and print it modulo $10^9+7$.

Input Format

The first line contains an integer $n$ $(3\leq n\leq10^5)$. The next line contains $n$ space-separated integers $a_1,a_2,\ldots,a_n$ $(1\leq a_i\leq n)$. Integer $a_i$ denotes the color of the ${i}$-th polygon vertex. All the vertices of the polygon are numbered from ${1}$ to $n$ in clockwise order.

You may assume that each $a_i$ was generated randomly, uniformly and independently from other values. For example, you may assume that $a_i=random(1,n)$ for each ${i}$. Where function $random(1,n)$ returns uniform integer from ${1}$ to $n$.

Output Format

Print a single integer $-$ the answer to the problem modulo $10^9+7$.

Sample Input #1

4
1 1 1 1

Sample Output #1

7

Sample Input #2

4
4 2 3 1

Sample Output #2

11

Source: hackerrank | Difficulty: MEDIUM
Tags: Probability


Solutions:
import os, sys, itertools, bisect
from collections import defaultdict, Counter
MOD = 10 ** 9 + 7
DEBUG = [False]

def mod_power(x, k):
	if k == 0:
		return 1
	p = 1
	while k:
		if k & 1:
			p = p * x % MOD
		x = x * x % MOD
		k = k // 2
	return p

def find_good_point(colors):
	N = len(colors)
	color_counts = Counter(colors)
	for (k, c) in enumerate(colors):
		leftSet = set()
		rightSet = set()
		bad = False
		for i in range(N - 1):
			c2 = colors[(k + 1 + i) % N]
			if c2 == c:
				bad = True
				break
			if c2 in rightSet:
				break
			rightSet.add(c2)
		if bad:
			continue
		for i in range(N - 1):
			c2 = colors[(k - 1 - i) % N]
			if c2 == c:
				bad = True
				break
			if c2 in leftSet:
				break
			leftSet.add(c2)
		if bad:
			continue
		if leftSet and rightSet and (not leftSet & rightSet):
			return k
	return None

def solve_recursive(colors):
	N = len(colors)
	color_counts = Counter(colors)
	color_to_most_recent = {}
	distance_to_previous = [None] * N
	for (k, c) in enumerate(colors):
		ilastc = color_to_most_recent.get(c)
		distance_to_previous[k] = None if ilastc is None else k - ilastc
		color_to_most_recent[c] = k

	def S(n):
		if n < 0:
			raise ValueError(n)
		if n == 0:
			return 1
		fn = distance_to_previous[n - 1]
		if fn is None:
			return 2 * S(n - 1)
		return 2 * S(n - 1) - T(n - 1, fn)

	def T(n, k):
		if k == 0:
			return S(n)
		fn = distance_to_previous[n - 1]
		if fn is None:
			return T(n - 1, k - 1)
		if k > fn:
			return 0
		return T(n - 1, k - 1) - T(n - 1, fn)
	if False and len(colors) == 3:
		print(f' ==> Sequence {colors}')
		print(f'S(3) = {S(3)}')
		print(f'S(2) = {S(2)}')
		print(f'S(1) = {S(1)}')
		print(f'S(0) = {S(0)}')
		print(f'f[3] = {distance_to_previous[2]}')
		print(f'f[2] = {distance_to_previous[1]}')
		print(f'T(2,1) = {T(2, 1)}')
		print(f'T(2,0) = {T(2, 0)}')
		print(f'T(1,1) = {T(1, 1)}')
		print(f'T(1,0) = {T(1, 0)}')
	return S(N)

def OBVIOUSLY_WRONG_solve(colors):
	N = len(colors)
	color_to_indices = defaultdict(list)
	indices = None
	for (k, c) in enumerate(colors):
		lst = color_to_indices[c]
		lst.append(k)
		if len(lst) >= 2:
			indices = lst
			break
	if not indices:
		return (mod_power(2, N) - N - 1) % MOD
	(k1, k2) = indices
	if k1 > k2:
		(k1, k2) = (k2, k1)
	path1 = colors[:k1] + colors[k1 + 1:]
	path2 = colors[:k2] + colors[k2 + 1:]
	path3 = colors[k1 + 1:k2]
	path4 = colors[k2 + 1:] + colors[:k1]
	color_counts = Counter(colors)
	hasColourRepeatedAtLeast3Times = False
	colorRepeatedTwiceCountLowerBound = 0
	for (c, count) in color_counts.items():
		if count == 2:
			colorRepeatedTwiceCountLowerBound += 1
		elif count >= 3:
			hasColourRepeatedAtLeast3Times = True
		if hasColourRepeatedAtLeast3Times or colorRepeatedTwiceCountLowerBound >= 2:
			break
	if hasColourRepeatedAtLeast3Times or colorRepeatedTwiceCountLowerBound >= 2:
		numberOfAdmissibleCoSingletons = 0
	elif colorRepeatedTwiceCountLowerBound >= 1:
		numberOfAdmissibleCoSingletons = 2
	else:
		numberOfAdmissibleCoSingletons = n
	count = (solve_path(path1) + solve_path(path2) - solve_path(path3) * solve_path(path4) - numberOfAdmissibleCoSingletons) % MOD
	return count

def solve_fallback(colors):
	n = len(colors)
	if not colors:
		return 0
	total_count = 0
	color_counts = Counter(colors)
	hasColourRepeatedAtLeast3Times = False
	colorRepeatedTwiceCountLowerBound = 0
	for (c, count) in color_counts.items():
		if count == 2:
			colorRepeatedTwiceCountLowerBound += 1
		elif count >= 3:
			hasColourRepeatedAtLeast3Times = True
		if hasColourRepeatedAtLeast3Times or colorRepeatedTwiceCountLowerBound >= 2:
			break
	if hasColourRepeatedAtLeast3Times or colorRepeatedTwiceCountLowerBound >= 2:
		numberOfAdmissibleCoSingletons = 0
	elif colorRepeatedTwiceCountLowerBound >= 1:
		numberOfAdmissibleCoSingletons = 2
	else:
		numberOfAdmissibleCoSingletons = n
	counts = Counter()
	for (k, c) in enumerate(colors):
		if k == 0:
			counts[tuple(), tuple()] = 1
			if color_counts[c] == 1:
				counts[tuple(), False] += 1
			else:
				counts[(c,), False] = 1
			continue
		elif k == n - 1:
			for ((left_set, right_set), count) in counts.items():
				total_count = (total_count + count) % MOD
				if right_set != False and c not in left_set and (c not in right_set) and (not set(left_set) & set(right_set)):
					total_count = (total_count + count) % MOD
			break
		prev_counts = counts
		counts = Counter()
		if color_counts[c] == 1:
			for ((left_set, right_set), count) in prev_counts.items():
				counts[left_set, tuple()] += count
				if right_set == False:
					counts[left_set, False] += count
				else:
					counts[left_set, right_set] += count
		else:
			for ((left_set, right_set), count) in prev_counts.items():
				counts[left_set, tuple()] += count
				if right_set == False:
					if c not in left_set:
						left_set2 = tuple(sorted(left_set + (c,)))
						counts[left_set2, False] += count
				elif c not in right_set:
					right_set2 = tuple(sorted(right_set + (c,)))
					counts[left_set, right_set2] += count
	total_count = (total_count - numberOfAdmissibleCoSingletons) % MOD
	return total_count

def solve(colors):
	N = len(colors)
	cut_point = find_good_point(colors)
	if cut_point is None:
		return solve_fallback(colors)
	path = colors[cut_point + 1:] + colors[:cut_point]
	color_counts = Counter(colors)
	hasColourRepeatedAtLeast3Times = False
	colorRepeatedTwiceCountLowerBound = 0
	for (c, count) in color_counts.items():
		if count == 2:
			colorRepeatedTwiceCountLowerBound += 1
		elif count >= 3:
			hasColourRepeatedAtLeast3Times = True
		if hasColourRepeatedAtLeast3Times or colorRepeatedTwiceCountLowerBound >= 2:
			break
	if hasColourRepeatedAtLeast3Times or colorRepeatedTwiceCountLowerBound >= 2:
		numberOfAdmissibleCoSingletons = 0
	elif colorRepeatedTwiceCountLowerBound >= 1:
		numberOfAdmissibleCoSingletons = 2
	else:
		numberOfAdmissibleCoSingletons = n
	count = (2 * solve_path(path) - numberOfAdmissibleCoSingletons) % MOD
	return count

def solve_path(colors):
	n = len(colors)
	color_counts = Counter(colors)
	color_to_most_recent = {}
	distance_to_previous = [None] * n
	for (k, c) in enumerate(colors):
		ilastc = color_to_most_recent.get(c)
		distance_to_previous[k] = None if ilastc is None else k - ilastc
		color_to_most_recent[c] = k
	total_count = 1
	T = [total_count]
	for (k, c) in enumerate(colors):
		fk = distance_to_previous[k]
		if fk is None:
			new_total = 2 * total_count % MOD
			T = [new_total] + T
			total_count = new_total
		else:
			dc = T[fk] if fk < len(T) else 0
			new_total = (2 * total_count - dc) % MOD
			T = [new_total] + [x - dc for x in T[:fk + 1]]
			total_count = new_total
	return total_count

def brute(colors):
	n = len(colors)
	count = 0
	for p in itertools.product([0, 1], repeat=n):
		k = sum(p)
		if k >= n - 1:
			continue
		curcomp = set()
		bad = False
		for (i, px) in enumerate(p):
			if not px:
				curcomp = set()
			else:
				c = colors[i]
				if c in curcomp:
					bad = True
					break
				curcomp.add(c)
		if not bad:
			for (i, px) in enumerate(p):
				if not px:
					break
				else:
					c = colors[i]
					if c in curcomp:
						bad = True
						break
					curcomp.add(c)
			if not bad:
				count = (count + 1) % MOD
	return count

def brute_path_no_conditions(colors):
	n = len(colors)
	count = 0
	for p in itertools.product([0, 1], repeat=n):
		k = sum(p)
		curcomp = set()
		bad = False
		for (i, px) in enumerate(p):
			if not px:
				curcomp = set()
			else:
				c = colors[i]
				if c in curcomp:
					bad = True
					break
				curcomp.add(c)
		if not bad:
			count = (count + 1) % MOD
	return count

def run_tests():
	path_mode = False
	continue_on_fail = os.environ.get('CONTINUE123') is not None
	always_print_failures = os.environ.get('PRINTFAIL123') is not None
	if path_mode:
		print('\n** Note: Testing match with path not cycle case\n')
	fail_count = 0
	test_case_count = 0
	sum_pct_error = 0
	max_error_diff = 0
	min_error_diff = 0
	for n in range(2, 9):
		if continue_on_fail and fail_count > 0:
			print(f'... {100 * fail_count / test_case_count:.3f}% = {fail_count} failed cases out of {test_case_count} with avg %error {sum_pct_error / test_case_count:.3f} and diff from {min_error_diff} to {max_error_diff}')
		print(f'Testing {n} ...')
		lastx0 = None
		for p in itertools.product(range(n), repeat=n):
			if p[0] != lastx0:
				lastx0 = p[0]
			if path_mode:
				ansexp = brute_path_no_conditions(p) % MOD
			else:
				ansexp = brute(p) % MOD
			ans = solve(p)
			test_case_count += 1
			if ans != ansexp:
				fail_count += 1
				if ansexp != 0:
					sum_pct_error += 100 * abs(ans - ansexp) / ansexp
					max_error_diff = max(max_error_diff, ans - ansexp)
					min_error_diff = min(min_error_diff, ans - ansexp)
				if always_print_failures or not continue_on_fail:
					print(f'FAIL: {p}: Got {ans} expected {ansexp}')
				if not continue_on_fail:
					break
			if continue_on_fail and fail_count > 0 and (test_case_count % 10000 == 0):
				print(f'... {100 * fail_count / test_case_count:.3f}% = {fail_count} failed cases out of {test_case_count} with avg %error {sum_pct_error / test_case_count:.3f} and diff from {min_error_diff} to {max_error_diff}')
		if fail_count and (not continue_on_fail):
			break
	if continue_on_fail and fail_count > 0:
		print(f'FAIL: {fail_count} failed cases out of {test_case_count} with avg %error {sum_pct_error / test_case_count:.3f} and diff from {min_error_diff} to {max_error_diff}')

def main():
	if os.environ.get('DEBUG123'):
		DEBUG[0] = True
	if os.environ.get('TEST123'):
		DEBUG[0] = False
		run_tests()
	else:
		n = int(sys.stdin.readline())
		colors = list(map(int, sys.stdin.readline().split()))
		print(solve(colors))
main()