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
xMAn: 2015-09-16 10:37:48

nice question to brush up your number theory skills

Vars: 2015-09-15 18:57:25

g8 question ... a reminder of 10th class maths...but updates caused several wa's

Last edit: 2015-09-16 17:48:39
Anant Upadhyay: 2015-09-15 13:45:53

Problem got better after rejudge......(^_^)

ASHUTOSH DWIVEDI: 2015-09-15 13:14:13

All solutions have been rejudged :)
Constraints have been changed.
Find your's bug

Last edit: 2015-09-16 00:15:05
shantanu tripathi: 2015-09-15 08:20:58

@shruti
No other test case will be provided :P

Last edit: 2015-09-15 08:56:20
Shruti Agarwal: 2015-09-15 07:49:45

what will be the output fr 1000000000!!!!!

ANIKET: 2015-09-13 11:57:14

Nice question 'Kudos' to problem setter

shantanu tripathi: 2015-09-12 21:26:44

first one to solve... #maths.

Aditya Agarwal: 2015-09-12 21:25:16

For the following test case:
2
2
1

What will the output be?
626
or
62
6
Reply
Ya 2nd one

Last edit: 2015-09-14 17:40:03

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