You are given an equation of the form x_{1}+x_{2}+...+x_{N}=K. You need to find the total number of positive integral solutions of this equation.
 
Example 1:
Input: s = a+b=5
Output: 4
Explanation: (4,1) , (1,4) , (2,3) , (3,2)
Example 2:
Input: s = a+b=1
Output: 0
Explanation: No solution exist.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function posIntSol() which takes a string as input and returns number of solutions.
Note: Distance has to be calculated with a precision of 0.0000000000001
Expected Time Complexity : O(Length of given string)
Expected Auxiliary Space : O(1)
 
Constraints:
1 <= K <= 25
2 <= N <= 10

Difficulty: MEDIUM
Tags: String algorithms

Combinatorics

Data structures

Mathematics
Skill types: Data structures
Expected Time Complexity: O(Length of given string)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3



class Solution:

    def posIntSol(self,s):

        #code here

Solutions:
class Solution:

	def posIntSol(self, s):
		i = 0
		pcnt = 0
		while s[i] != '=':
			if s[i] == '+':
				pcnt += 1
			i += 1
		r = pcnt + 1
		n = ''
		i += 1
		while i < len(s):
			n += s[i]
			i += 1
		n = int(n)
		n = n - r
		if n <= 0:
			return 0
		cnt = 0
		num = 1
		den = 1
		while cnt < n:
			num = num * (n + r - 1 - cnt)
			den = den * (cnt + 1)
			cnt += 1
		return num // den


from math import factorial as fact

class Solution:

	def posIntSol(self, s):
		r = 1
		n = ''
		for i in range(len(s)):
			if s[i] == '+':
				r += 1
			if s[i] == '=':
				n = s[i + 1:]
				break
		n = int(n)
		if n - 1 >= r - 1:
			return fact(n - 1) // (fact(n - r) * fact(r - 1))
		else:
			return 0


class Solution:

	def posIntSol(self, s):
		fact = lambda n: 1 if n <= 1 else n * fact(n - 1)
		r = 1
		n = ''
		for i in range(len(s)):
			if s[i] == '+':
				r += 1
			if s[i] == '=':
				n = s[i + 1:]
				break
		n = int(n)
		return fact(n - 1) // (fact(n - r) * fact(r - 1)) if n - 1 >= r - 1 else 0


class Solution:

	def posIntSol(self, s):
		n = s.count('+') + 1
		k = int(s.split('=')[1])
		if k < n:
			return 0
		num = 1
		i = n - 1 + 1
		while i <= k - 1:
			num = num * i
			i += 1
		den = 1
		i = 1
		while i <= k - n:
			den = den * i
			i += 1
		return num // den


from math import factorial

class Solution:

	def posIntSol(self, s):
		targ = []
		for i in range(len(s) - 1, -1, -1):
			if s[i].isnumeric():
				targ.append(s[i])
		target = int(''.join(targ[::-1]))
		variable = (len(s) - 2 + 1) // 2
		if variable > target:
			return 0
		return factorial(target - 1) // (factorial(variable - 1) * factorial(target - variable))


import math
from math import factorial as fact

class Solution:

	def posIntSol(self, s):
		x = s.split('=')
		container = len(x[0].strip().split('+'))
		tot = int(x[1].strip())
		if container > tot:
			return 0
		else:
			return fact(tot - 1) // (fact(container - 1) * fact(tot - container))


import math

class Solution:

	def posIntSol(self, s):
		p = s.split('=')
		x = len(p[0]) - p[0].count('+')
		if x > int(p[1]):
			return 0
		else:
			v = math.factorial(int(p[1]) - 1)
			n = math.factorial(x - 1) * math.factorial(int(p[1]) - x)
			return int(v / n)


class Solution:

	def posIntSol(self, s):
		lis = list(s.split('='))
		k = int(lis[1]) - 1
		n = int((len(lis[0]) + 1) / 2) - 1
		if k < n or k < 0 or n < 0:
			return 0
		else:
			numer = 1
			dinom = 1
			for i in range(1, n + 1):
				numer *= k - i + 1
				dinom *= i
			return int(numer / dinom)


class Solution:

	def posIntSol(self, s):
		count = 0
		nums = 0
		for i in range(len(s)):
			if s[i] == '+':
				count += 1
			if s[i] == '=':
				t = s[i + 1:]
				break
		nums = int(t) - 1
		i = nums
		n1 = 1
		n2 = 1
		while i > nums - count:
			n1 *= i
			i -= 1
		i = 1
		while i <= count:
			n2 *= i
			i += 1
		return n1 // n2


class Solution:

	def posIntSol(self, s):
		l = s.split('=')
		d = int(l[1])
		g = l[0].count('+')
		p = d - g
		s = 1
		h = 1
		for i in range(g):
			s *= p
			p += 1
			h *= i + 1
		return s // h


class Solution:

	def posIntSol(self, s):
		n = 0
		for i in range(len(s)):
			if s[i] == '+':
				n += 1
			if s[i] == '=':
				k = int(s[i + 1:])
		k = k - 1
		k_fact = self.factorial(k)
		n_fact = self.factorial(n)
		k_min_n_fact = self.factorial(k - n)
		ans = int(k_fact / (n_fact * k_min_n_fact))
		return ans

	def factorial(self, value):
		fact = 1
		for i in range(2, value + 1):
			fact *= i
		return fact


class Solution:

	def nCr(self, n, r):
		if r > n:
			return 0
		if r > n - r:
			r = n - r
		res = 1
		for i in range(r):
			res = res * (n - i)
			res = res // (i + 1)
		return res

	def posIntSol(self, s):
		(left, k) = s.split('=')
		variablesCount = len(left.split('+'))
		return self.nCr(int(k) - 1, variablesCount - 1)


class Solution:

	def posIntSol(self, s):
		mod = 1000000000.0 + 7
		N = 0
		n = len(s)
		for i in range(n):
			if s[i] == '+':
				N += 1
			elif s[i] == '=':
				Y = int(s[i + 1:])
		ans = self.fact(Y - 1) / (self.fact(Y - N - 1) * self.fact(N)) % mod
		return int(ans)

	def fact(self, n):
		i = 1
		for j in range(1, n + 1):
			i = i * j
		return i


class Solution:

	def posIntSol(self, s):

		def fac(n):
			f = 1
			for i in range(1, n + 1):
				f *= i
			return f
		k = s.count('+')
		i = s.index('=')
		n = int(s[i + 1:])
		return fac(n - 1) // (fac(k) * fac(n - k - 1))


class Solution:

	def posIntSol(self, s):
		n = sum((1 if i == '+' else 0 for i in s)) + 1
		k = int(s.split('=')[1])
		DP = [[-1 for j in range(k + 1)] for i in range(n + 1)]

		def solve(n, k):
			if k < n:
				return 0
			if n == 0:
				return 1 if k == 0 else 0
			if DP[n][k] > 0:
				return DP[n][k]
			c = 0
			for i in range(1, k + 1):
				c += solve(n - 1, k - i)
			DP[n][k] = c
			return c
		return solve(n, k)


class Solution:

	def posIntSol(self, s):
		r = s.count('+')
		t = s.index('=')
		k = int(s[t + 1:]) - 1
		if r == 0:
			return 1
		if r == 1:
			return k
		fact = 1
		while r > 0:
			fact *= k / r
			k -= 1
			r -= 1
		return round(fact)


class Solution:

	def posIntSol(self, s):
		var = 1
		n = len(s)
		for i in range(n):
			if s[i] == '+':
				var += 1
		right = 0
		j = 1
		i = n - 1
		while i >= 0:
			if s[i] == '=':
				break
			else:
				right = int(s[i]) * j + right
				j *= 10
			i -= 1
		left_num = right - var
		return int(self.nCr(left_num + var - 1, var - 1))

	def nCr(self, n, r):
		return self.fact(n) / (self.fact(r) * self.fact(n - r))

	def fact(self, n):
		res = 1
		for i in range(2, n + 1):
			res = res * i
		return res


from math import factorial as fac

class Solution:

	def posIntSol(self, s):
		count = 0
		k = 0
		c = 0
		for i in s:
			if i == '+':
				count += 1
			if i == '=':
				k = c
			c += 1
		var = count + 1
		n = int(s[k + 1:]) - 1
		r = var - 1
		if n <= 0 or r > n:
			return 0
		else:
			return fac(n) // (fac(n - r) * fac(r))


import math

class Solution:

	def posIntSol(self, s):
		N = int(s.split('=')[-1])
		if N == 1:
			return 0
		N -= 1
		R = s.count('+')
		if R >= N:
			return 0
		res = 1
		for i in range(R + 1, N + 1):
			res = res * i
		for i in range(1, N - R + 1):
			res = res / i
		return math.ceil(res)


def fact(n):
	if n == 0 or n == 1:
		return 1
	return fact(n - 1) * n

class Solution:

	def posIntSol(self, s):
		n = s.split('=')[-1]
		r = len(s) - 1 - s.count('+') - len(n)
		n = int(n)
		f = fact
		if n - 1 < 0 or r - 1 < 0 or n - r < 0 or (n < r):
			return 0
		return f(n - 1) // (f(r - 1) * f(n - r))


class Solution:
	memo = {}

	def factorial(self, n):
		if n <= 1:
			return 1
		if n in self.memo:
			return self.memo[n]
		self.memo[n] = n * self.factorial(n - 1)
		return self.memo[n]

	def posIntSol(self, s):
		cnt = 0
		n = 0
		for i in range(len(s)):
			if s[i] == '+':
				cnt += 1
			if s[i] == '=':
				n = int(s[i + 1:])
		if n - cnt - 1 <= 0:
			return 0
		return self.factorial(n - 1) // (self.factorial(n - 1 - cnt) * self.factorial(cnt))


import math

class Solution:

	def posIntSol(self, s):
		c = (s.index('=') + 1) // 2
		k = int(s[s.index('=') + 1:])
		a = math.factorial
		if k < c:
			return 0
		else:
			return int(a(k - 1) // (a(c - 1) * a(k - c)))


class Solution:

	def posIntSol(self, s):
		if not s:
			return 0
		subStrings = s.split('=')
		summination = int(subStrings[1])
		numbers = subStrings[0].split('+')
		N = summination - 1
		k = len(numbers) - 1
		A = 1
		for i in range(k):
			A *= N - i
		factorial = 1
		for i in range(1, k + 1):
			factorial *= i
		return A // factorial


class Solution:

	def posIntSol(self, s):
		if s:
			tokens = s.split('=')
			lhs = tokens[0]
			targetSum = int(tokens[1])
			variables = len(lhs.split('+'))
			memo = {}
			return self.findNumberOfSolns(variables, targetSum, memo)
		else:
			return 0

	def findNumberOfSolns(self, variables, targetSum, memo):
		if variables == 0 and targetSum == 0:
			return 1
		elif variables < 0 or targetSum < 0:
			return 0
		if variables in memo:
			if targetSum in memo[variables]:
				return memo[variables][targetSum]
		if targetSum < variables:
			return 0
		else:
			result = 0
			for i in range(1, targetSum - variables + 2):
				numSubSolns = self.findNumberOfSolns(variables - 1, targetSum - i, memo)
				if numSubSolns > 0:
					result += numSubSolns
			if variables in memo:
				memo[variables][targetSum] = result
			else:
				memo[variables] = {targetSum: result}
			return result


class Solution:

	def posIntSol(self, s):

		def fac(n):
			if n == 1:
				return 1
			return n * fac(n - 1)
		r = 0
		idx = 0
		while True:
			if s[idx] == '+':
				r += 1
			if s[idx] == '=':
				n = int(s[idx + 1:]) - 1
				break
			idx += 1
		if r > n:
			return 0
		else:
			return fac(n) // (fac(n - r) * fac(r))


import math

class Solution:

	def posIntSol(self, s):
		val = 0
		n = 0
		ind = 0
		for (i, c) in enumerate(s):
			if c == '+':
				n += 1
			if c == '=':
				ind = i + 1
				break
		val = int(s[i + 1:]) - 1
		if n + 1 > val:
			return 0
		return int(math.factorial(val) / (math.factorial(val - n) * math.factorial(n)))


class Solution:

	def posIntSol(self, s):
		eqs = s.split('=')
		variables = eqs[0].split('+').__len__()
		value = int(eqs[1])
		return int(self.ncr(value - 1, variables - 1))

	def ncr(self, n, r):
		if n == 0:
			return 0
		if n < r:
			return 0
		fac = list()
		fac.append(1)
		for i in range(1, n + 1):
			fac.append(fac[i - 1] * i)
		ans = fac[n] / (fac[n - r] * fac[r])
		return ans


from math import factorial

class Solution:

	def posIntSol(self, s):
		st = str(s)
		n = 1
		for i in range(len(st)):
			if st[i] == '+':
				n += 1
			elif st[i] == '=':
				k = int(st[i + 1:])
				break
		if k - 1 >= n - 1:
			return factorial(k - 1) // (factorial(k - n) * factorial(n - 1))
		else:
			return 0


class Solution:

	def fact(self, n):
		ans = 1
		for i in range(2, n + 1):
			ans *= i
		return ans

	def posIntSol(self, s):
		MOD = 1000000000.0 + 7
		index = 0
		r = 0
		for i in range(len(s)):
			if s[i] == '+':
				r += 1
			if s[i] == '=':
				index = i
		n = int(s[index + 1:]) - 1
		num = 1
		for i in range(1, r + 1):
			num *= n
			n -= 1
		den = self.fact(r)
		return num // den


import math

class Solution:

	def posIntSol(self, s):
		l = len(s)
		if l % 2 == 0:
			n = l // 2 - 1
		else:
			n = l // 2
		k = int(s[l - 1])
		if s[l - 2] >= '0' and s[l - 2] <= '9':
			h = int(s[l - 2])
			k = h * 10 + k
		if k < n:
			return 0
		elif n == k:
			return 1
		else:
			a = math.factorial(k - 1)
			b = math.factorial(n - 1)
			c = math.factorial(k - n)
			return a // (b * c)


from math import factorial

class Solution:

	def posIntSol(self, s):
		l = len(s)
		try:
			K = int(s[-2]) * 10 + int(s[-1])
		except:
			K = int(s[-1])
		N = 0
		for i in range(0, l):
			if s[i] == '=':
				break
			elif s[i] != '+':
				N += 1
		if K < N:
			return 0
		ans = int(factorial(K - 1) / (factorial(N - 1) * factorial(K - N)))
		return ans


class Solution:

	def binomialCoefficient(self, n, k):
		if k > n - k:
			k = n - k
		res = 1
		for i in range(k):
			res = res * (n - i)
			res = res // (i + 1)
		return res

	def posIntSol(self, s):
		n = 0
		k = 0
		le = len(s)
		for i in range(le):
			if s[i] == '+':
				n += 1
			elif s[i] == '=':
				n += 1
				k = int(s[i + 1:])
				break
		k -= n
		if k < 0:
			return 0
		return self.binomialCoefficient(n + k - 1, n - 1)


import math

class Solution:

	def posIntSol(self, s):
		r = 0
		plus = 0
		l = 0
		for i in s:
			if i <= 'z' and i >= 'a':
				r += 1
			elif i == '+':
				plus += 1
			l += 1
		n = int(s[r + plus + 1:])
		if n >= r:
			ans = int(math.factorial(n - 1) / (math.factorial(r - 1) * math.factorial(n - r)))
			return ans
		else:
			return 0


class Solution:

	def factorial(self, n):
		return 1 if n == 1 or n == 0 else n * self.factorial(n - 1)

	def posIntSol(self, s):
		r = s.count('+')
		n = int(s.split('=')[-1]) - 1
		if n < r:
			return 0
		n_fact = self.factorial(n)
		r_fact = self.factorial(r)
		n_r_fact = self.factorial(n - r)
		return n_fact // (r_fact * n_r_fact)


class Solution:

	def fact(self, a):
		mul = 1
		for i in range(1, a + 1):
			mul = mul * i
		return mul

	def posIntSol(self, s):
		r = len(s.split('+'))
		x = s.split('=')
		n = int(x[-1])
		n = n - 1
		r = r - 1
		if n - 1 > 0 and r - 1 >= 0:
			p = self.fact(n) / (self.fact(n - r) * self.fact(r))
			return int(p)
		else:
			return 0


def fact(n):
	if n < 0:
		return 1
	if n == 0:
		return 1
	return n * fact(n - 1)

class Solution:

	def posIntSol(self, s):
		s = s.split('=')
		n = int(s[1])
		r = len(s[0].split('+'))
		return fact(n - 1) // (fact(r - 1) * fact(n - r))


import math

class Solution:

	def posIntSol(self, s):
		r = 0
		n = 0
		for i in range(len(s)):
			if s[i] == '+':
				r += 1
			if s[i] == '=':
				n = int(s[i + 1:])
		if n < r + 1:
			return 0
		r += 1
		n = n - 1
		r = r - 1
		return int(math.factorial(n) / (math.factorial(r) * math.factorial(n - r)))


import math

class Solution:

	def posIntSol(self, s):
		size = len(''.join(['1' for ele in s if ele.isalpha()]))
		K = ''.join([ele for ele in s if ele.isdecimal()])
		K = int(K)
		if K == size:
			return 1
		elif K < size:
			return 0
		else:
			a = math.factorial(K - 1)
			b = math.factorial(size - 1)
			c = math.factorial(K - 1 - (size - 1))
			return int(a / b / c)


import math

class Solution:

	def nCr(self, n, r):
		if n < 0 or r < 0 or n - r < 0:
			return 0
		f = math.factorial
		return int(f(n) / f(r) / f(n - r))

	def posIntSol(self, s):
		if s and len(s) == 0:
			return 0
		expression = s.split('=')
		summation = int(expression[-1])
		gap = len(expression[0].split('+'))
		if gap == 1:
			return 1
		if summation < gap:
			return 0
		else:
			return self.nCr(summation - 1, gap - 1)


class Solution:

	def posIntSol(self, s):

		def calcula(valores, resultado):
			if valores == 0:
				return 1
			else:
				return resultado * calcula(valores - 1, resultado - 1) / valores
		valores = s.split('=')
		resultado = int(valores[-1])
		val = len(valores[0].split('+'))
		if resultado < val:
			return 0
		else:
			return int(calcula(val - 1, resultado - 1))


class Solution:

	def posIntSol(self, s):

		def fac(x):
			fac = 1
			for i in range(1, x + 1):
				fac *= i
			return fac
		lis = list(map(str, s.strip().split('=')))
		n = int(len(lis[0]) - len(lis[0]) // 2)
		k = int(lis[1])
		result = int(fac(k - 1) / (fac(n - 1) * fac(k - n)))
		return result


import math

class Solution:

	def posIntSol(self, s):
		parts = s.split('+')
		N = len(parts)
		K = int(s.split('=')[-1])
		if N > K:
			return 0
		if N < 1:
			return 0
		if K < 1:
			return 0
		return int(math.factorial(K - 1) / (math.factorial(N - 1) * math.factorial(K - N)))


class Solution:
	co = 0

	def posIntSol(self, s):
		l = s.split('+')
		no_of_var = len(l)
		r = l[-1].split('=')
		rhs = int(r[-1])
		lim = int(rhs) - (no_of_var - 1)
		rh = rhs - 1
		r1 = no_of_var - 1
		an = self.nCr(rh, r1)
		return int(an)

	def nCr(self, n, r):
		return self.fact(n) / (self.fact(r) * self.fact(n - r))

	def fact(self, nm):
		if nm == 0:
			return 1
		f = 1
		for i in range(1, nm + 1):
			f = f * i
		return f


class Solution:

	def posIntSol(self, s):
		eq = s.index('=')
		k = int(s[eq + 1:])
		ss = s[:eq]
		n = len(ss.split('+'))

		def nCr(n, r):
			return fact(n) / (fact(r) * fact(n - r))

		def fact(n):
			res = 1
			for i in range(2, n + 1):
				res = res * i
			return res
		rem = k - n
		if rem < 0:
			return 0
		return int(nCr(rem + n - 1, n - 1))


class Solution:

	@staticmethod
	def get_factorial(v):
		fact = 1
		for i in range(2, v + 1):
			fact *= i
		return fact

	def posIntSol(self, s: str):
		(eqn, val) = s.split('=')
		(r, n) = (len(eqn.split('+')), int(val))
		if n < r:
			return 0
		n_min_1_fac = self.get_factorial(n - 1)
		r_min_1_fac = self.get_factorial(r - 1)
		n_min_r_fac = self.get_factorial(n - r)
		return n_min_1_fac // (n_min_r_fac * r_min_1_fac)


from math import *

class Solution:

	def posIntSol(self, s):
		pos = s.index('=')
		k = int(s[pos + 1:])
		n = s.count('+') + 1
		if k - 1 >= 0 and n - 1 >= 0 and (k - n >= 0):
			ans = factorial(k - 1) // (factorial(n - 1) * factorial(k - n))
			return ans
		return 0


class Solution:

	def posIntSol(self, s):

		def fact(n):
			factor = 1
			if n == 1 or n == 0:
				factor *= 1
			else:
				factor = n * fact(n - 1)
			return factor
		count = 0
		num = 0
		for i in s:
			if i.isalpha():
				count += 1
			if i.isdigit():
				num *= 10
				num += int(i)
		if num >= count:
			soln = fact(num - 1) / (fact(count - 1) * fact(num - count))
		else:
			return 0
		return int(soln)


class Solution:

	def posIntSol(self, s):

		def fact(n):
			if n == 0:
				return 1
			return n * fact(n - 1)
		st = False
		c = 0
		val = ''
		for i in s:
			if i == '+':
				c += 1
			if st:
				val += i
			if i == '=':
				st = True
		val = int(val) - 1
		if val < c:
			return 0
		return fact(val) // (fact(val - c) * fact(c))


import math

class Solution:

	def posIntSol(self, s):
		st = s.split('+')
		k = st[-1][2:]
		r = len(st)
		n = int(k)
		if r >= n:
			if n == r:
				return 1
			else:
				return 0
		return int(math.factorial(n - 1) / math.factorial(n - r) / math.factorial(r - 1))


class Solution:

	def posIntSol(self, s):
		arr = s.split('=')
		n = int(arr[-1])
		arr_new = str(arr[0]).split('+')
		r = len(arr_new)

		def factorial(num):
			prod = 1
			for i in range(1, num + 1, 1):
				prod *= i
			return prod
		num = factorial(n - 1)
		deno = factorial(n - r) * factorial(r - 1)
		return int(num / deno)


import math

class Solution:

	def posIntSol(self, s):

		def comb(n, k):
			k = min(k, n - k)
			if k == 1:
				return n
			ans = 1
			for i in range(k):
				ans *= n - i
				ans //= i + 1
			return ans
		equal_to_at = s.find('=')
		(k, n) = (equal_to_at // 2 + 1, int(s[equal_to_at + 1:]))
		if k > n:
			return 0
		return comb(n - 1, k - 1)


class Solution:

	def posIntSol(self, s):
		unknown = 1
		n = len(s)
		for i in range(1, n):
			if s[i] == '+':
				unknown += 1
			if s[i] == '=':
				k = int(s[i + 1:])
				break
		if k < unknown:
			ans = 0
		elif k == unknown:
			ans = 1
		else:
			k -= 1
			unknown -= 1
			ans = 1
			for i in range(k - unknown + 1, k + 1):
				ans *= i
			for i in range(1, unknown + 1):
				ans //= i
		return ans


class Solution:

	def posIntSol(self, s):
		k = int(s.split('=')[1])
		n = len(s.split('+')) - 1

		def facts(n):
			if n < 2:
				return 1
			else:
				return n * facts(n - 1)
		ans = facts(k - 1) // (facts(k - n - 1) * facts(n))
		return ans


class Solution:

	def posIntSol(self, s):
		list1 = s.split('=')
		equation = list1[0]
		total = list1[1]
		r = equation.split('+')
		up = int(total) - 1
		down = int(len(r)) - 1
		up1 = self.factorial(up)
		down1 = self.factorial(down)
		down2 = self.factorial(up - down)
		final_output = int(up1 / (down1 * down2))
		return final_output

	def factorial(self, N):
		M = 1
		for i in range(1, N + 1):
			M = M * i
		return M


class Solution:

	def posIntSol(self, s):
		n = s[s.index('=') + 1:]
		m = s[:s.index('=')]
		c = m.split('+')
		r = len(c)
		t = q = 1
		for i in range(1, r):
			t *= int(n) - i
			q *= i
		return t // q


class Solution:

	def help(self, n, k):
		if k < n:
			return 0
		elif n == 1:
			return 1
		else:
			return sum([self.help(n - 1, k - i) for i in range(1, k - n + 2)])

	def posIntSol(self, s):
		i = len(s) - 1
		n = 1
		k = 0
		while i >= 0:
			if s[i] == '=':
				k = int(s[i + 1:])
				n = (i + 1) // 2
				break
			else:
				i = i - 1
		return self.help(n, k)


class Solution:

	def posIntSol(self, s):

		def fac(n):
			if n == 1:
				return 1
			return n * fac(n - 1)
		n = int(s[s.find('=') + 1:]) - 1
		t = 0
		for i in range(len(s)):
			if s[i] == '+':
				t += 1
		if t > n:
			return 0
		else:
			return fac(n) // (fac(n - t) * fac(t))


import math

class Solution:

	def posIntSol(self, s):
		(exp, b) = s.split('=')
		k = len(exp.split('+'))
		b = int(b)
		if b < k:
			return 0

		def nCr(n, r):
			f = math.factorial
			return f(n) // f(r) // f(n - r)
		return nCr(b - 1, k - 1)


import math

class Solution:

	def posIntSol(self, s):

		def fact(i):
			if i < 2:
				return 1
			return i * fact(i - 1)

		def nck(n, k):
			return fact(n) // (fact(k) * fact(n - k))
		(x, n) = s.split('=')
		n = int(n)
		x = (len(x) + 1) // 2
		if n < x:
			return 0
		return nck(n - 1, x - 1)


class Solution:

	def posIntSol(self, s):
		a = s.split('=')
		r = a[0].count('+') + 1
		n = int(a[1])

		def fact(q):
			if q == 0:
				return 1
			else:
				return q * fact(q - 1)
		if n - 1 >= r - 1:
			return int(fact(n - 1) / (fact(n - r) * fact(r - 1)))
		else:
			return 0


class Solution:

	def posIntSol(self, s):
		num = s.split('+')
		n = ''
		for ch in num[-1][::-1]:
			if ch == '=':
				break
			n = ch + n
		n = int(n)
		var = len(num)
		n -= var
		if n >= 0:
			a = var - 1
			b = n
			n += a
			if a < b:
				(a, b) = (b, a)
			nr = dr = 1
			for i in range(a + 1, n + 1):
				nr *= i
			for i in range(1, b + 1):
				dr *= i
			ans = int(nr / dr)
		else:
			ans = 0
		return ans


import math

class Solution:

	def posIntSol(self, s):
		k = s.index('=')
		if s[k + 1:] == '1':
			return 0
		elif s[k + 1:] == '0':
			return 1
		else:
			c = 0
			for i in range(len(s)):
				if s[i] == '+':
					c += 1
			if c >= int(s[k + 1:]):
				return 0
			else:
				t = int(s[k + 1:]) - 1
				m = math.factorial(t) // (math.factorial(c) * math.factorial(t - c))
				return m


class Solution:

	def posIntSol(self, s):
		arr = s.split('+')
		r = len(arr) - 1
		n = int(arr[-1].split('=')[-1]) - 1
		if n < r:
			return 0
		elif r == n:
			return 1
		else:
			r = max(r, n - r)
			ans = 1
			for i in range(r + 1, n + 1):
				ans = ans * i
			for i in range(1, n - r + 1):
				ans = ans // i
			return ans