Given an integer S represented as a string, the task is to get the sum of all possible sub-strings of this string.
As the answer will be large, print it modulo 10^9+7.
Example 1:
Input:
S = 1234
Output: 1670
Explanation: Sum = 1 + 2 + 3 + 4 + 12 +
23 + 34 + 123 + 234 + 1234 = 1670
Example 2:
Input:
S = 421
Output: 491
Explanation: Sum = 4 + 2 + 1 + 42 + 21
Your Task:
You only need to complete the function sumSubstrings that takes S as an argument and returns the answer modulo 1000000007.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
Constraints:
1 <= |S| <= 10^{4}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Dynamic programming

Data structures

Starter code: #User function Template for python3



class Solution:

    #Function to find sum of all possible substrings of the given string.

    def sumSubstrings(self,s):

        

        # code here

Solutions:
class Solution:

	def sumSubstrings(self, s):
		n = len(s)
		digits = []
		for char in s:
			digits.append(int(char))
		dp = [0 for i in range(n)]
		dp[0] = digits[0]
		res = dp[0]
		for i in range(1, n):
			dp[i] = ((i + 1) * digits[i] + dp[i - 1] * 10) % 1000000007
			res += dp[i]
			res %= 1000000007
		return res


class Solution:

	def sumSubstrings(self, s):
		a = s
		dp = [0 for i in range(len(a))]
		dp[0] = int(a[0])
		result = dp[0]
		for i in range(1, len(a)):
			dp[i] = (i + 1) * int(a[i]) + 10 * dp[i - 1]
			result = result + dp[i]
		return result % (10 ** 9 + 7)


class Solution:

	def sumSubstrings(self, s):
		ls = []
		for i in s:
			ls.append(int(i))
		p = ls[0]
		s = ls[0]
		for j in range(1, len(ls)):
			c = ls[j]
			temp = (j + 1) * c + p * 10
			s = s + temp
			p = temp
		return s % 1000000007


class Solution:

	def sumSubstrings(self, num):
		mod = 1000000007
		n = len(num)
		prev = int(num[0])
		result = prev
		cur = 0
		for i in range(1, n):
			cur = (i + 1) * int(num[i]) + 10 * prev
			result += cur
			prev = cur
		return result % mod


class Solution:

	def sumSubstrings(self, s):
		M = 1000000007
		n = len(s)
		dp = [0 for i in range(0, n)]
		dp[0] = ord(s[0]) - ord('0')
		for i in range(1, n):
			dp[i] = ((i + 1) * (ord(s[i]) - ord('0')) + 10 * dp[i - 1]) % M
		ans = 0
		for i in range(0, n):
			ans += dp[i] % M
		return ans % M


class Solution:

	def sumSubstrings(self, s):
		dp = [0] * len(s)
		dp[0] = int(s[0])
		mod = 10 ** 9 + 7
		for i in range(1, len(s)):
			dp[i] = (10 * dp[i - 1] + int(s[i]) * (i + 1)) % mod
		res = 0
		for i in range(len(s)):
			res += dp[i]
			res %= mod
		return res


class Solution:

	def sumSubstrings(self, s):
		n = len(s)
		prev = int(s[0])
		res = prev
		current = 0
		for i in range(1, n):
			numi = int(s[i])
			current = (i + 1) * numi + 10 * prev
			res += current
			prev = current
		return res % 1000000007


class Solution:

	def sumSubstrings(self, s):
		sub_res = 0
		prev_res = int(s[0])
		res = prev_res
		mod = 1000000000.0 + 7
		for i in range(1, len(s)):
			sub_res = ((i + 1) * int(s[i]) + 10 * prev_res) % mod
			res = (res + sub_res) % mod
			prev_res = sub_res
		return int(res)


class Solution:

	def sumSubstrings(self, s):
		dp = [0] * len(s)
		dp[0] = int(s[0])
		for i in range(1, len(s)):
			dp[i] = (dp[i - 1] * 10 + (i + 1) * int(s[i])) % 1000000007
		return sum(dp) % 1000000007


class Solution:

	def sumSubstrings(self, s):
		su = 0
		mod = 1000000007
		n = len(s)
		dp = [0] * n
		dp[0] = int(s[0])
		for i in range(1, n):
			dp[i] = 10 * dp[i - 1] % mod + (i + 1) * int(s[i])
		for i in range(n):
			su = (su + dp[i]) % mod
		return su


class Solution:

	def sumSubstrings(self, s):
		ans = 0
		k = 1
		for i in range(len(s) - 1, -1, -1):
			ans = ans + int(s[i]) * (i + 1) * k
			k = k * 10 + 1
		return ans % 1000000007


class Solution:

	def sumSubstrings(self, s):
		summa = 0
		n = len(s)
		for i in range(n):
			summa += int('1' * (n - i)) * int(s[i]) * (i + 1)
		return summa % (10 ** 9 + 7)


class Solution:

	def sumSubstrings(self, s):
		n = len(s)
		total = 0
		mod = 10 ** 9 + 7
		for i in range(n):
			text = s[i] * (n - i)
			total += int(text) * (i + 1)
		return total % mod


class Solution:

	def sumSubstrings(self, s):
		no = [int(s[0])]
		ans = no[0]
		MOD = 1000000007
		for i in range(1, len(s)):
			curr = (i + 1) * int(s[i]) + no[-1] * 10
			no.append(curr % MOD)
			ans += no[i]
		return ans % MOD


class Solution:

	def sumSubstrings(self, s):
		n = len(s)
		l = [0] * (n + 1)
		l[0] = ord(s[0]) - ord('0')
		for i in range(1, n):
			l[i] = (ord(s[i]) - ord('0')) * (i + 1) + 10 * l[i - 1]
		sum = 0
		m = pow(10, 9) + 7
		for d in l:
			sum = (sum + d) % m
		return sum


class Solution:

	def sumSubstrings(self, s):
		n = len(s)
		mod = 1000000007
		ls = [0] * n
		ls[0] = int(s[0]) % mod
		for i in range(1, n):
			ls[i] = ((i + 1) * int(s[i]) + 10 * ls[i - 1]) % mod
		add = 0
		for i in range(n):
			add += ls[i]
		return add % mod


class Solution:

	def sumSubstrings(self, s):
		m = 10 ** 9 + 7
		n = len(s)
		L = []
		L.append(int(s[0]))
		res = L[0]
		for i in range(1, n):
			p = int(s[i])
			L.append((i + 1) * p + 10 * L[i - 1])
			res = res + L[i]
		return res % m


class Solution:

	def sumSubstrings(self, s):
		M = 10 ** 9 + 7
		sum_val = 0
		B = 1
		res = 0
		for i in range(len(s) - 1, -1, -1):
			res = (res + int(s[i]) * B * (i + 1)) % M
			sum_val -= int(s[i])
			B = (B * 10 + 1) % M
		return res


class Solution:

	def sumSubstrings(self, s):
		mod = 10 ** 9 + 7
		ans = 0
		n = len(s)
		pref_arr = [0] * n
		pref_arr[0] = int(s[0])
		for i in range(1, n):
			val = (i + 1) * int(s[i])
			pref_arr[i] = val + 10 * pref_arr[i - 1]
		for i in range(n):
			ans += pref_arr[i] % mod
		return ans % mod


class Solution:

	def sumSubstrings(self, s):
		n = len(s)
		res = []
		res.append(int(s[0]))
		for i in range(1, n):
			si = int(s[i])
			res.append((i + 1) * si + 10 * res[i - 1])
		summ = sum(res) % (10 ** 9 + 7)
		return summ


def fun(s, n):
	dp = [0] * n
	m = 10 ** 9 + 7
	dp[0] = int(s[0])
	sum = dp[0]
	for i in range(1, n):
		dp[i] = ((i + 1) * int(s[i]) + 10 * dp[i - 1]) % m
		sum += dp[i]
		sum %= m
	return sum

class Solution:

	def sumSubstrings(self, s):
		n = len(s)
		return fun(s, n)


class Solution:

	def sumSubstrings(self, s):
		mod = 10 ** 9 + 7
		sum1 = 0
		p = 1
		for i in range(len(s) - 1, -1, -1):
			sum1 = (sum1 + int(s[i]) * (i + 1) * p) % mod
			p = p * 10 + 1
		return sum1


class Solution:

	def sumSubstrings(self, s):
		(st, m) = (0, 1)
		for i in range(len(str(s)) - 1, -1, -1):
			st += int(str(s[i])) * (i + 1) * m
			m = m * 10 + 1
		return st % (10 ** 9 + 7)
import atexit
import io
import sys
import sys
sys.setrecursionlimit(10 ** 6)
if __name__ == '__main__':
	test_cases = int(input())
	for cases in range(test_cases):
		s = str(input())
		ob = Solution()
		print(ob.sumSubstrings(s))


class Solution:

	def sumSubstrings(self, s):
		ans = 0
		n = len(s)
		a = 1
		dp = [0] * n
		for i in range(n):
			dp[i] = a
			a = a * 10
		for i in range(1, n):
			dp[i] += dp[i - 1]
		for i in range(len(s)):
			ans += (i + 1) * int(s[i]) * dp[n - i - 1]
			ans = ans % (10 ** 9 + 7)
		return ans
import atexit
import io
import sys
import sys
sys.setrecursionlimit(10 ** 6)
if __name__ == '__main__':
	test_cases = int(input())
	for cases in range(test_cases):
		s = str(input())
		ob = Solution()
		print(ob.sumSubstrings(s))


class Solution:

	def sumSubstrings(self, s):
		mat = []
		s1 = str(s)
		mat.append(s1[0])
		for i in range(1, len(s1)):
			val = int(str(mat[i - 1]) + '0')
			val1 = int((i + 1) * int(s1[i]))
			ans = val + val1
			mat.append(ans)
		res = 0
		for i in mat:
			res = res + int(i)
		return res % 1000000007


class Solution:

	def sumSubstrings(self, num):
		n = len(num)
		prev = int(num[0])
		res = prev
		current = 0
		for i in range(1, n):
			numi = int(num[i])
			current = (i + 1) * numi + 10 * prev
			res += current
			prev = current
		return res % (10 ** 9 + 7)


class Solution:

	def sumSubstrings(self, s):
		dp = [0] * (len(s) + 1)
		dp[0] = int(s[0])
		res = dp[0]
		for i in range(1, len(s)):
			dp[i] = (i + 1) * int(s[i]) + 10 * dp[i - 1]
			res += dp[i]
		return res % 1000000007
import atexit
import io
import sys
import sys
sys.setrecursionlimit(10 ** 6)
if __name__ == '__main__':
	test_cases = int(input())
	for cases in range(test_cases):
		s = str(input())
		ob = Solution()
		print(ob.sumSubstrings(s))


class Solution:

	def sumSubstrings(self, s):
		mod = int(1000000000.0 + 7)
		n = len(s)
		totSum = int(s[0])
		prevSum = int(s[0])
		for i in range(1, n):
			curSum = (i + 1) * int(s[i]) + 10 * prevSum
			totSum = (totSum % mod + curSum % mod) % mod
			prevSum = curSum
		return totSum


class Solution:

	def sumSubstrings(self, s):
		res = []
		s1 = str(s)
		sum0 = []
		sum0.append(int(s1[0]))
		for i in range(1, len(s)):
			sum1 = int(s1[i]) * (i + 1) + 10 * sum0[i - 1]
			sum0.append(sum1)
		return sum(sum0) % 1000000007


class Solution:

	def sumSubstrings(self, s):
		p = 1000000007
		il = 0
		el = 0
		n = 0
		for i in s:
			i = int(i)
			el = (il + el) % p
			il = (il * 10 + n * i + i) % p
			n += 1
		return (il + el) % p


class Solution:

	def sumSubstrings(self, string):
		sum = int(string[0])
		n = len(string)
		pre_sum = int(string[0])
		for i in range(1, n):
			pre_sum = int(string[i]) * (i + 1) + 10 * pre_sum
			sum += pre_sum
		return sum % 1000000007


class Solution:

	def sumSubstrings(self, s):
		mod = 1000000007
		sum = 0
		for i in range(len(s)):
			num = int(s[i] * (len(s) - i)) % mod * (i + 1) % mod % mod
			sum += num % mod
		return sum % mod


class Solution:

	def sumSubstrings(self, s):
		mod = 1000000007
		n = len(s)
		if n == 0:
			return 0
		if n == 1:
			return int(s[0])
		dp = [0] * (n + 1)
		dp[0] = 0
		res = 0
		for i in range(1, n + 1):
			dp[i] = (i * (int(s[i - 1]) % mod) % mod + 10 * dp[i - 1] % mod % mod) % mod
			res = (res % mod + dp[i] % mod) % mod
		return res % mod
		dp[1] = int(s[0]) % mod
		dp[2] = int(s[0]) % mod + int(s[1]) % mod + int(s[0:2]) % mod
		for i in range(3, n + 1):
			res = 0
			for j in range(i):
				res += int(s[j:i]) % mod
			dp[i] = (res % mod + dp[i - 1] % mod) % mod


class Solution:

	def sumSubstrings(self, s):
		st = [int(s[0])]
		res = st[0]
		for i in range(1, len(s)):
			p = int(s[i])
			st.append((i + 1) * p + 10 * st[-1])
			res += st[-1]
		return res % 1000000007


class Solution:

	def sumSubstrings(self, s):
		ans = 0
		x = 1
		c = len(s)
		for i in s[::-1]:
			ans += x * int(i) * c
			x = x * 10 + 1
			c -= 1
		return ans % 1000000007


class Solution:

	def sumSubstrings(self, s):
		mod = 1000000007
		n = len(s)
		lst = [0 for i in range(n)]
		lst[0] = int(s[0])
		res = int(s[0])
		for i in range(1, n):
			lst[i] = (i + 1) * int(s[i]) + 10 * lst[i - 1]
			res += lst[i]
		return res % mod


class Solution:

	def sumSubstrings(self, s):
		sums = 0
		multiply = 1
		for i in range(len(s) - 1, -1, -1):
			sums += int(s[i]) * (i + 1) * multiply
			multiply = multiply * 10 + 1
		return sums % (10 ** 9 + 7)


class Solution:

	def sumSubstrings(self, s):
		string_number = str(s)
		a = [0] * len(string_number)
		a[0] = int(s[0])
		for i in range(1, len(string_number)):
			a[i] = 10 * a[i - 1] + (i + 1) * int(string_number[i])
		return sum(a) % 1000000007


class Solution:

	def sumSubstrings(self, s):
		mod = 10 ** 9 + 7
		result = 0
		N = len(s)
		sum_of_digits = [int(s[0])]
		for i in range(1, N):
			result = (int(s[i]) * (i + 1) + 10 * sum_of_digits[i - 1]) % mod
			sum_of_digits.append(result)
		return sum(sum_of_digits) % mod


class Solution:

	def sumSubstrings(self, s):
		if len(s) == 0:
			return 0
		mod = 1000000007
		dp = [0 for _ in range(len(s))]
		dp[0] = int(s[0])
		result = dp[0]
		for i in range(1, len(s)):
			dp[i] = (i + 1) * int(s[i]) + 10 * dp[i - 1] % mod
			result += dp[i] % mod
		return result % mod


from itertools import combinations

class Solution:

	def sumSubstrings(self, s):
		(current, result) = (int(s[0]), 0)
		for i in range(len(s) - 1):
			result += current
			prev = current
			current = (i + 2) * int(s[i + 1]) + 10 * prev
		return (result + current) % 1000000007


from itertools import combinations

class Solution:

	def sumSubstrings(self, s):
		c = 0
		q = int(s[0])
		res = q
		for i in range(1, len(s)):
			ni = int(s[i])
			c = (i + 1) * ni + 10 * q
			res += c
			q = c
		return res % 1000000007


class Solution:

	def sumSubstrings(self, s):
		l = [0] * len(s)
		l[0] = int(s[0])
		for i in range(1, len(s)):
			x = int(s[i])
			y = l[i - 1]
			l[i] = x * (i + 1) + 10 * y
		return sum(l) % 1000000007


class Solution:

	def sumSubstrings(self, s):
		n = len(s)
		koo = 10 ** 9 + 7
		arr = [0] * n
		arr[0] = int(s[0])
		for i in range(1, n):
			arr[i] = arr[i - 1] + int(s[i]) * (i + 1)
		ans = 0
		for i in range(n):
			ans = (ans % koo + arr[i] * 10 ** (n - i - 1) % koo) % koo
		return ans % koo


class Solution:

	def sumSubstrings(self, s):
		ans = [int(s[0])]
		for i in range(1, len(s)):
			a = ans[i - 1] * 10 + int(s[i]) * (i + 1)
			ans.append(a)
		return sum(ans) % 1000000007


class Solution:

	def sumSubstrings(self, s):
		su = 0
		mf = 1
		for i in range(len(s) - 1, -1, -1):
			su = su + int(s[i]) * (i + 1) * mf
			mf = mf * 10 + 1
		return su % (10 ** 9 + 7)


class Solution:

	def sumSubstring(s, n):
		if n == 0:
			return 0
		su = int(s[n - 1])
		su += Solution.sumSubstring(s, n - 1) % 1000000007
		for i in range(n - 2, -1, -1):
			su += int(s[i:n])
		return su

	def sumSubstrings(self, s):
		n = len(s)
		dp = [0] * (n + 1)
		dp[0] = int(s[0])
		res = dp[0]
		for i in range(1, n):
			dp[i] = (i + 1) * int(s[i]) + 10 * (dp[i - 1] % 1000000007)
			res += dp[i]
		return res % 1000000007


class Solution:

	def sumSubstrings(self, s):
		n = len(s)
		sod = []
		sod.append(int(s[0]))
		res = sod[0]
		for i in range(1, n):
			numi = int(s[i])
			sod.append((i + 1) * numi + 10 * sod[i - 1])
			res += sod[i]
		return res % (10 ** 9 + 7)


class Solution:

	def sumSubstrings(self, s):
		n = len(s)
		dp = [0] * n
		res = int(s[0])
		dp[0] = res
		m = 1000000007
		for i in range(1, n):
			dp[i] = (i + 1) * int(s[i]) + 10 * dp[i - 1] % m
			res = (res + dp[i]) % m
		return res


class Solution:

	def sumSubstrings(self, str):
		modulo = 1000000007
		dp = [0] * len(str)
		dp[0] = int(str[0])
		for i in range(1, len(str)):
			dp[i] = (dp[i - 1] + int(str[i]) + (dp[i - 1] - (dp[i - 2] if i > 1 else 0)) * 10 + int(str[i]) * i) % modulo
		return dp[-1]


class Solution:

	def sumSubstrings(self, s):
		M = 1000000007
		n = len(s)
		sumstr = []
		sumstr.append(int(s[0]))
		res = sumstr[0]
		for i in range(1, n):
			sumstr.append((i + 1) * int(s[i]) + 10 * sumstr[i - 1])
			res += sumstr[i]
		return res % M


class Solution:

	def sumSubstrings(self, s):
		mod = 10 ** 9 + 7
		n = len(s)
		s = str(s)
		dp = [0] * n
		dp[0] = int(s[0])
		ans = dp[0]
		for i in range(1, n):
			dp[i] = ((i + 1) * int(s[i]) + 10 * dp[i - 1]) % mod
			ans = (ans + dp[i]) % mod
		return ans


class Solution:

	def sumSubstrings(self, s):
		n = len(s)
		sumofdigit = []
		sumofdigit.append(int(s[0]))
		res = sumofdigit[0]
		for i in range(1, n):
			numi = int(s[i])
			sumofdigit.append((i + 1) * numi + 10 * sumofdigit[i - 1])
			res += sumofdigit[i]
		return res % 1000000007


class Solution:

	def sumSubstrings(self, s):
		t = 0
		i = 0
		f = len(s)
		a = []
		r = 0
		a.append(1)
		for i in range(1, len(s)):
			a.append(a[i - 1] * 10 + 1)
		for x in range(0, len(s)):
			r = r + a[x] * int(s[f - 1 - x]) * (f - x)
		return r % 1000000007


class Solution:

	def sumSubstrings(self, s):
		if len(s) == 0:
			return 0
		prev = int(s[0])
		total = prev
		for i in range(2, len(s) + 1):
			curr = int(s[i - 1]) * i + 10 * prev
			total += curr
			prev = curr
		return total % 1000000007


class Solution:

	def sumSubstrings(self, s):
		n = len(s)
		a = [int(i) for i in s]
		dp = [0 for i in range(n)]
		dp[0] = a[0]
		c = dp[0]
		for i in range(1, n):
			dp[i] = ((i + 1) * a[i] + 10 * dp[i - 1]) % 1000000007
			c += dp[i] % 1000000007
		return c % 1000000007


mod = 10 ** 9 + 7

class Solution:

	def sumSubstrings(self, s):
		prev = int(s[0])
		ans = prev
		for i in range(1, len(s)):
			curr = int(s[i])
			val = (i + 1) * curr + 10 * prev
			ans = (ans + val) % mod
			prev = val
		return ans