Fibonacci concatenation solution codechef
Let’s define Fibonacci concatenation sequence as follows:
, for every
Heredenotes the Fibonacci concatenation number and represents concatenation.
For example,, .
Given an integer, you have to determine the sum of digits of all subsequences of the Fibonacci concatenation number , modulo .
A subsequence of a number is a sequence of digits that can be derived from the number by deletion of several (possibly, zero or all) digits without changing the order of the remaining digits. The subsequence may even start with trailing zeros. For example, are subsequences of while is NOT a subsequence of . Note that there are subsequences of . The subsequence appears twice and should be counted as different while computing the sum.
Input Format Fibonacci concatenation solution codechef
- The first line of the input contains a single integer denoting the number of test cases. The description of test cases follows.
- The first and only line of each test case contains a single integer .
Output Format Fibonacci concatenation solution codechef
For each test case, print a single line containing one integer – the sum of digits of all subsequences of, modulo .
Constraints Fibonacci concatenation solution codechef
Sample Input 1
3 1 2 3
Sample Output 1
1 2 8
Test case: Since , we have only two subsequences, “” (empty subsequence) and “ “. So the sum of digits of both subsequences is .
Test case: Since , we have four subsequences, “” (empty subsequence), “ “, “ ” and “ “. So the sum of digits of all the subsequences is .
Solution: Click here