Algorithm
Problem link- https://www.spoj.com/problems/SUMMUL/
SUMMUL - Sum of products
One boy Petya decided to practice in addition and multiplication of numbers. For this he chose some positive integer n, and ordered all the ways to decompose it into two or more terms of positive integers, and the ways in different order terms are considered to be different (for example, for n = 3 there are three ways: 1 + 2, 2 + 1 and 1 + 1 + 1). Then he replaced all the plus signs with multiplication, and added the results (for n = 3: 1 × 2 + 2 × 1 + 1 × 1 × 1 = 5). After practicing for the day he decided to check the correctness of his calculations. Help Petya find the right answers.
Input
The first line contains T (1 <= T <= 1000) - the number of tests. Following T lines contain n (1 <= n <= 10 ^ 9).
Output
For each n from the input print the result Petya should get modulo 1000000007.
Example
Input: 3 1 2 3 Output: 0 1 5
Code Examples
#1 Code Example with Python Programming
Code -
Python Programming
class matrix:
a = []
def __init__(self, default=None):
if default is not None:
self.a = default
else:
self.a = [[0, 0], [0, 0]]
def __mul__(self, other):
s = matrix()
for i in range(2):
for j in range(2):
for k in range(2):
s.a[i][j] += self.a[i][k] * other.a[k][j]
for i in range(2):
for j in range(2):
s.a[i][j] %= 1000000007
return s
def __pow__(self, power, modulo=None):
if power == 1:
return matrix([[1, 1], [1, 0]])
if power % 2 == 1:
return self * (self.__pow__(power - 1))
half = self.__pow__(power // 2)
return half * half
def get(n, modulo):
m = matrix([[1, 1], [1, 0]]) ** n
return m.a[0][1]
modulo = 1000000007
T = int(input())
for _ in range(T):
N = int(input())
print((get(N * 2, modulo) - N + modulo) % modulo)Input
2
3
Output
1
5
Demonstration
SPOJ Solution-Sum of products-Solution in C, C++, Java, Python