# DCP-342: Marvel’s Smartest Back to All Problems

Medium Divide and Conquer > Dynamic Programming

**Amedeus Cho** helped **Bruce Banner** survive a radiation explosion and in the process he was exposed to the gamma radiation, becoming the “Totally Awesome Hulk”. Amedeus , with the help of his genious sister Madame Cho, roams in New York and fights crime with a chilled mood, turning into a jolly yet gruesome Hulk. Amedues is ranked as the 8th smartest person in the Marvel Universe, behind Hank Pym, Moon Girl, Bruce Banner, Tony Stark, Hank McCoy, Dr.Doom, T’Chala. But Madame Cho thinks her brother is naive and not smarter than her. To test Amedeus’s intelligence, she thought of a mathematical question. And here she is, Madame Cho, asking him the question, “ Let us call a **n-digit** number (n is an integer , **1<=n<=100000**) a Meme-number if it consists of digits from **0,1,2,3,4** and the difference between any two consecutive digit in the number is exactly two. How many n-digit numbers are there who are Meme-numbers?” Input: ------ Input will consist of N+1 lines in separate line ( **1<=N <=100000**) First line will contain N, the number of values of **n**. Next N line will contain one integer each denoting the value of n. Output: ------- For each n, print the number of n-digit numbers which are Meme-numbers. You should print the answer modulo **10^9+7**. Sample Input ------------ 2 1 2 Sample Output ------------- 5 6 Explanation: There are 2 inputs: n=1,2 For n=1, possible Meme-numbers are { 0, 1, 2, 3, 4}=>5 For n=2, possible Meme-numbers are {20, 31, 02, 42,13, 24}=>6

### Problem Limits

 Language Time Limit (seconds) C 1.00 C++ 1.00 C++14 1.00 C# 2.00 Go 2.00 Java 2.00 JavaScript 2.00 Objective-C 2.00 Perl 2.00 PHP 2.00 Python 2.00 Python3 2.00 Ruby 2.00 VB.Net 2.00

# 51/133

Solve/Submission

### Ranking

# User Language Timing
01 prodipdatta7 Cpp14 0.00s
02 swapnilsaha Cpp14 0.00s
03 kissu_pari_na Cpp 0.00s
04 moshiur_cse15 Cpp14 0.00s
05 Morass Cpp14 0.00s
06 prateepm Cpp14 0.01s
07 robin_aust Cpp 0.01s
08 Double_O Cpp14 0.01s
09 ssavi Cpp14 0.01s
10 feodorv C 0.01s
12 sazal_dev Cpp 0.01s
13 emrul Cpp14 0.01s
14 nasif2587 Cpp14 0.01s
15 mno123 Cpp 0.01s
16 shaft Cpp 0.01s
17 njrafi Cpp14 0.02s
18 alttlprgrmmng Cpp 0.02s
19 nafiz0080 Cpp14 0.02s
20 Zeronfinity Cpp14 0.02s
21 dmehrab06 Cpp14 0.02s
22 Mahmudul_Tushar Cpp 0.02s
23 Islam_Rafat Cpp14 0.02s
24 ksohan Cpp 0.02s
25 as_couple Cpp14 0.02s
26 Ishrak Cpp 0.02s
27 AlaminJust Cpp14 0.02s
28 tariqiitju Cpp14 0.03s
29 Sarwar05 Cpp 0.03s
30 nasib_mbstu Cpp 0.03s
31 I_See_You Cpp14 0.03s
32 Masum_ice Cpp14 0.03s
33 Foysol_Ahmed Cpp 0.03s
34 haasib Cpp 0.03s
35 vatsalsharma376 Cpp14 0.03s
36 mahbubcseju Cpp14 0.03s
37 rayhan50001 Cpp 0.04s
38 clkjwdhc Cpp 0.05s
Feedback