DISTRIBUTE BOOKS | Code vita 2019

Problem Description 

For enhancing the book reading, school distributed story books to students as part of the Children’s day celebrations.
To increase the reading habit, the class teacher decided to exchange the books every weeks so that everyone will have a different book to read. She wants to know how many possible exchanges are possible.
If they have 4 books and students, the possible exchanges are 9. Bi is the book of i-th student and after the exchange he should get a different book, other than Bi.

B1 B2 B3 B4 - first state, before exchange of the books
B2 B1 B4 B3
B2 B3 B4 B1
B2 B4 B1 B3
B3 B1 B4 B2
B3 B4 B1 B2
B3 B4 B2 B1
B4 B1 B2 B3
B4 B3 B1 B2
B4 B3 B2 B1

Find the number of possible exchanges, if the books are exchanged so that every student will receive a different book.

Constraints 

1<= N <= 1000000

Input Format 

Input contains one line with N, indicates the number of books and number of students.

Output 

Output the answer modulo 1000000007.

Example 1

Input

4

Output

9

GROOVING MONKEYS | Code via

Problem Description

N monkeys are invited to a party where they start dancing. They dance in a circular formation, very similar to a Gujarati Garba or a Drum Circle. The dance requires the monkeys to constantly change positions after every 1 second.

The change of position is not random & you, in the audience, observe a pattern. Monkeys are very disciplined & follow a specific pattern while dancing.

Consider N = 6, and an array monkeys = {3,6,5,4,1,2}.

This array (1-indexed) is the dancing pattern. The value at monkeys[i], indicates the new of position of the monkey who is standing at the ith position.

Given N & the array monkeys[ ], find the time after which all monkeys are in the initial positions for the 1st time.

Constraints

1<=t<=10 (test cases)

1<=N<=10000 (Number of monkeys)

Input Format

First line contains single integer t, denoting the number of test cases.

Each test case is as follows -

Integer N denoting the number of monkeys.

Next line contains N integer denoting the dancing pattern array, monkeys[].

Output

t lines,

Each line must contain a single integer T, where T is the minimum number of seconds after which all the monkeys are in their initial position.

Example 1

Input

1

6

3 6 5 4 1 2

Output

6

Explanation

Consider N = 6, and an array monkeys = {3,6,5,4,1,2}.

Suppose monkeys are a,b,c,d,e,f, & Initial position (at t = 0) -> a,b,c,d,e,f

At t = 1 -> e,f,a,d,c,b

a will move to 3rd position, b will move to 6th position, c will move to 5th position, d will move to 4th position, e will move to 1st position and f will move to 2nd position. Thus from a,b,c,d,e,f at t =0, we get e,f,a,d,c,b at t =1. Recursively applying same transpositions, we get following positions for different values of t.

At t = 2 -> c,b,e,d,a,f

At t = 3 -> a,f,c,d,e,b

At t = 4 -> e,b,a,d,c,f

At t = 5 -> c,f,e,d,a,b

At t = 6 -> a,b,c,d,e,f

Since at t = 6, we got the original position, therefore the answer is 6.

BALANCING STARS | CODE VITA 2019

Problem Description

CODU loves to play with string of brackets.

He considers string as a good string if it is balanced with stars. A string is considered as balanced with stars if string contains balanced brackets and between every pair of bracket i.e. between opening and closing brackets, there are at least 2 stars(*) present. CODU knows how to check whether a string is balanced or not but this time he needs to keep a track of stars too. He decided to write a program to check whether a string is good or not. But CODU is not as good in programming as you are, so he decided to take help from you. Will you help him for this task? You need to print Yes and number of balanced pair if string satisfies following conditions(string is good if it satisfies following 2 conditions):

1. The string is balanced with respect to all brackets.

2. Between every pair of bracket there is at least two stars.

However if string doesn't satisfies above conditions then print No and number of balanced pair in string as an output.

Constraints

4 <= String length <= 1000

Input Format

The first and only line of input contains a string of characters(a-z,A-Z), numbers(0-9), brackets( '{', '[', '(', ')', ']', '}' ) and stars(*).

Output

Print space separated "Yes" (without quotes) and number of balanced pair if string is good. Else print "No" (without quotes) and number of balanced pair.

Example 1

Input

{**}

Output

Yes 1

Explanation

Here string contains one balanced pair {} and between this pair of bracket there are 2 stars present so the output is Yes with the count of balanced pair as 1.

Example 2

Input

{**(**{**[**]})}

Output

Yes 4

Explanation

String has balanced brackets and also satisfies 2nd condition. So the output is Yes with count of balanced pair which is 4.

Example 3

Input

**}xasd[**]sda231

Output

No 1

Explanation

In this case string is not balanced. So the output is No with the count of balanced pair as 1.

NEW ATM DESIGN | CODE VITA 2019

Problem Description

Automated Teller Machine (ATM) is an electronic device that enables people to withdraw cash from their bank account. Every ATM has a limit for number of currency notes (say N), it can give at a time.

A bank wants to design an ATM for school students. The unique feature of this ATM would be that it would always give maximum number of currency notes possible, to make the students happy.  Available denomination of currency notes in the ATM are 100, 200, 500, 1000

Constraints

N<100

Input Format

First Line provides an integer, N

Second Line provides an integer denoting the amount you want to withdraw (in multiples of 100)

Third Line provides an integer denoting the available currency note of Rs 100 in the ATM

Fourth Line provides an integer denoting the available currency note of Rs 200 in the ATM

Fifth Line provides an integer denoting the available currency note of Rs 500 in the ATM

Sixth Line provides an integer denoting the available currency note of Rs 1000 in the ATM

Output

One line containing the maximum number of currency note possible for the desired withdrawal amount. Output should be 0 (zero) if transaction is not possible, for example if sufficient fund is not available in the ATM.

Example 1

Input

10

1300

10

10 

10

10

Output

10

Explanation

Here,

7 * 100 + 3* 200 + 0*500 +0*1000 hence maximum possible currency = 10. 

Example 2

Input

5

1700

1

2

2

2

Output

3

Explanation

Here,

0 * 100  + 1 * 200 + 1 * 500 +1 * 1000 hence maximum possible currency = 3.

EXCHANGE DIGITS | CODE VITA 2019

Problem Description

Compute nearest larger number by interchanging digits updated.

Given 2 numbers a and b find the smallest number greater than b by interchanging the digits of a and if not possible print -1.

Constraints

1 <= a,b <= 10000000

Input Format

2 numbers, a and b, separated by space.

Output

A single number, greater than than b.

If not possible, print -1.

Example 1

Input

459 500

Output

549

Example 2

Input

645757 457765

Output

465577

Example 3

Input

5964 9984

Output

-1