Problem

Submissions

Solution

New

Discuss

1

Avg. time to solve

15 min

Success Rate

86%

Problem Statement

Suggest Edit

```
Let’s say N = 2. The strings of length 2, which satisfy the given constraints are: “aa”, “ab”, “ac”, “ba”, “bc”, “ca”, “cb”, “cc”. Hence, the output is 8.
```

```
The first line of input contains an integer ‘T’ representing the number of test cases.
The first and the only line of every test case contains a positive integer ‘N’ representing the length of strings to be found.
```

```
For each test case, the number of strings of length ‘N’ which satisfy the given constraints is printed.
Print the output of each test case in a separate line.
```

```
Since the number of possible strings can be very large, print the answer modulo 1000000007.
You do not need to print anything, it has already been taken care of. Just implement the given function.
```

```
Can you solve the problem in constant time and using constant extra space i.e. O(1) time and space complexity?
```

```
1 <= T <= 100
1 <= N <= 3000
Where 'T' denotes the number of test cases, 'N' denotes the length of strings.
Time Limit: 1 sec
```

```
2
2
3
```

```
8
19
```

```
For the first test case, refer to the example explained before.
For the second test case, N = 3. The strings of length 3, which satisfy the given constraints are: “aaa”, “aab”, “aac”, “aba”, “abc”, “aca”, “acb”, “acc”, and so on. There are a total of 19 possible strings.
```

```
2
4
1
```

```
39
3
```

Console