ADST01 - Truncky Numbers


Asutosh is very passionate about numbers. he has found a new type of numbers and calls them 'truncky numbers'.

He has challenged his friend Shantanu to find the sum of first n truncky numbers. As shantanu is weak at programming, help him to complete his challenge.

A truncky number is defined as:

  1. sum of digits in the number is of the form (5*k + 1) where k = number of digits.
  2. absolute difference between any two digits in the number is either 0 or 1.
  3. digits are in the non decreasing order.

Input

the first line contains T (number of test cases). Each test contains only one integer n.

Output

Print in single line sum of first n truncky numbers modulo 10^9 + 7.

Each output in new line.

Constraints

T <= 30

N <= 10^17

Example

Input:
1
2

Output:
62

hide comments
challenger_76: 2021-01-24 09:07:36

digits should be strictly increasing.

lakshya1st: 2020-09-01 17:54:13

Simple Math+Modular expo!! AC in one go :)

aryan29: 2019-01-24 13:22:49

please someone help me out I am not able to find mistake in my code it is showing wrong ans. I have used right formula for gp and I think I am using modular arithmetic in right way

sanchit_aga: 2019-01-12 16:16:56

Poor problem statement

mynk322: 2018-09-05 19:58:47

use GP sum, simple multiplication and modular expo...

sherlock11: 2018-03-31 20:48:23

make sure that problem states that "difference between any two digits is 0/1 not between any two consecutive digits" because of this i have wasted a lot of hours .....................but regarding the problem its simple

ankit1cool: 2017-06-13 09:35:01

Good question but problem statement had to be more clear.digits are in non decreasing order is confusing

and_roid: 2017-06-04 14:17:03

Good Question to solve !!

Last edit: 2017-06-04 14:17:34
conquistador: 2017-05-15 18:48:23

if some body solves this question in c++ . please post you solution link . i am really struggling with mod

sy_117: 2016-07-30 20:26:38

After a long finally done it !!! math+modular expo.


Added by:Voldemort
Date:2015-09-12
Time limit:0.100s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: GOSU
Resource:own