Given 3 characters 'a', 'b', 'c'. Find the number of strings of length n that can be formed from these 3 characters. Given that : we can use ‘a’ as many times as we want, ‘b’ maximum once, and ‘c’ maximum twice.
 
Example 1:
Input: n = 2
Output: 8
Expalantion: There are total 8 possible
strings and these are: {aa, ab, ba, ac,
ca, bc, cb, cc}.
Example 2:
Input: n = 3
Output: 19
Explanation: There are total 19 possible
strings.
 
Your Task:
You don't need to read or print anything. Your task is to complete the function no_ofString() which takes n as input parameter ans returns the no. of total possible strings than can be formed using characters 'a', 'b' and 'c' modulo 10^{9} + 7.
 
Expected Time Complexity: O(n)
Expected Space Compelxity: O(n)
 
Constraints:
1 <= n <= 100000

Source: geeksforgeeks | Difficulty: EASY
Tags: Combinatorics

Mathematics

Starter code: #User function Template for python3

class Solution:
	def no_ofString(self, n):
		# Code here

Solutions:
class Solution:

	def no_ofString(self, n):
		l = 10 ** 9 + 7
		return (1 + n * 2 + n * (n * n - 1) // 2) % l


class Solution:

	def no_ofString(self, n):
		m = 1000000007
		ans = 1 + 2 * (n % m) + n % m * (n % m - 1) * (n % m + 1) // 2
		return ans % m


class Solution:

	def no_ofString(self, n):
		return (n * n * n + (3 * n + 2)) // 2 % 1000000007


class Solution:

	def no_ofString(self, n):
		m = 1000000007
		ans = 1 + 2 * (n % m) + n % m * (n % m - 1) * (n % m + 1) // 2
		return ans % m
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		ob = Solution()
		ans = ob.no_ofString(n)
		print(ans)


class Solution:

	def no_ofString(self, n):
		m = 10 ** 9 + 7
		ans = 1 + 2 * (n % m) + n % m * (n % m - 1) * (n % m + 1) // 2
		return ans % m


class Solution:

	def no_ofString(self, n):
		if n == 1:
			return 3
		mod = int(10 ** 9 + 7)
		total = 1 + n % mod + n * n % mod + n * (n - 1) * (n - 1) // 2 % mod
		return total % mod


class Solution:

	def no_ofString(self, n):
		if n == 1:
			return 3
		total = 0
		for i in range(3):
			combination = 1
			bottom_part = 1
			for x in range(i):
				combination *= n - x
				bottom_part *= x + 1
			total = (total + combination // bottom_part) % (10 ** 9 + 7)
		for i in range(3):
			combination = 1
			bottom_part = 1
			for x in range(i):
				combination *= n - 1 - x
				bottom_part *= x + 1
			total = (total + n * (combination // bottom_part)) % (10 ** 9 + 7)
		return total


def possibilities(x):
	count = 1
	while x > 1:
		count *= x
		x -= 1
	return count

class Solution:

	def no_ofString(self, n):
		if n == 1:
			return 3
		all_a = 1
		one_b_other_a = n % (10 ** 9 + 7)
		one_c_other_a = n % (10 ** 9 + 7)
		one_c_one_b = n % (10 ** 9 + 7)
		if n > 2:
			one_c_one_b = n * (n - 1) % (10 ** 9 + 7)
		two_c = 1
		if n > 2:
			two_c = int(n * (n - 1) / 2) % (10 ** 9 + 7)
		one_b_two_c = 0
		if n > 2:
			one_b_two_c = int(n * (n - 1) * (n - 2) / 2) % (10 ** 9 + 7)
		return (all_a + one_b_other_a + one_c_other_a + one_c_one_b + two_c + one_b_two_c) % (10 ** 9 + 7)