# 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 swapnilsaha Cpp14 0.00s
02 prodipdatta7 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 emrul Cpp14 0.01s
08 ssavi Cpp14 0.01s
09 feodorv C 0.01s
11 robin_aust Cpp 0.01s
12 sazal_dev Cpp 0.01s
13 Double_O Cpp14 0.01s
14 shaft Cpp 0.01s
15 mno123 Cpp 0.01s
16 nasif2587 Cpp14 0.01s
17 Mahmudul_Tushar Cpp 0.02s
18 dmehrab06 Cpp14 0.02s
19 alttlprgrmmng Cpp 0.02s
20 njrafi Cpp14 0.02s
21 Zeronfinity Cpp14 0.02s
22 nafiz0080 Cpp14 0.02s
23 Islam_Rafat Cpp14 0.02s
24 ksohan Cpp 0.02s
25 as_couple Cpp14 0.02s
26 AlaminJust Cpp14 0.02s
27 Ishrak Cpp 0.02s
28 Sarwar05 Cpp 0.03s
29 nasib_mbstu Cpp 0.03s
30 haasib Cpp 0.03s
31 vatsalsharma376 Cpp14 0.03s
32 I_See_You Cpp14 0.03s
33 mahbubcseju Cpp14 0.03s
34 Masum_ice Cpp14 0.03s
35 tariqiitju Cpp14 0.03s
36 Foysol_Ahmed Cpp 0.03s
37 rayhan50001 Cpp 0.04s
38 clkjwdhc Cpp 0.05s
Feedback