Description

Johnny is a three years old kid. He likes to eat sugar. One day, he sneaked into the kitchen in order to grab some sugar to eat. Unfortunately, his papa catched him.

His papa called him: " Johnny, Johnny! "

Johnny replied: " Yes, papa. "

papa then asked: " Eating sugar? "

Johnny lied: " No, papa. "

At that moment, Johnny began to think that what's defintion of string equivalent?

---

Johnny thinks that string a and string b is equivalent if a and b are the same or string a and string b can be devided into two same size part: a₁, a₂, b₁, b₂ and the following rules fulfill：

(  ( a1 == b1 ) && ( a2 == b2 ) )  or  ( ( a1 == b2 ) && ( a2 == b1 ) )

In above sentence, "==" means whether a and b are the same or string a and string b can be devided into two same size part: a₁, a₂, b₁, b₂ and the following rules fulfill: (  ( a1 == b1 ) && ( a2 == b2 ) )  or  ( ( a1 == b2 ) && ( a2 == b1 ) ). You can consider this equal definition as a recursion.

For example: 

a = " papa ", b = " apap ", we need to check if " pa " equals " ap " in Johnny ' s rule.

Therefore, we divide " pa " into "p" and "a", and divide "ap" into "a" and "p". 

Then, because "p" == "p" && " a " == "a", we know that "pa" == "ap".

Hence, we can conclude that " papa " equals " apap ".

 

Note that we can't divide a string if the length of the string is an odd number.

Help Johnny find out whether the two string are the same. If you help him, he will give you some sugar.

 

 

 

 

Input

input contains two lines.

First line is the string a. 

Second line is the string b. 

the length of the two string are the same and the length is from 1~10⁵ ( 1 <= length <= 10⁵ )

 

Output

output contains one line.

print "YES" if two string is equal in Johnny's rule,

print "NO" otherwise.

remember to print \n at the end of output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

PaPa suspected that Johnny ate the sugar, yet Johnny said he hadn't eaten it.

Therefore, PaPa asked: " Telling lies? "

Johnny replied: " No PaPa. "

PaPa then demanded: " Open your mouth! "

Johnny laughed embarrassedly: " Ha Ha Ha!!! "

PaPa is so furious with Johnny telling lies, so he punished Johnny to do some math.

---

PaPa gave Johnny n numbers a₁ ~ a_n and a number k.

PaPa asked Johnny to calculate how many ways he could pick some numbers from a₁ to a_n in order to make their sum equal to k?

For example:

Given n = 5 and numbers are { 1,2,3,3,3 }, and k = 3, the answer is 4.

(Note that although there are three identical "3", we still consider them as different indentities.) { (1, 2), (3), (3), (3) }

Johnny is a bad boy, so he commands you to do this for him!

 

 

Input

Input contains two lines.

First line contains two integer n ( 1 <= n <= 20 ), k ( 1<=  k <=10⁹)

Second line contains n integer a₁ ~ a_n ( 1 <= a_i <= 10⁷ )

 

Output

Output only contains one integer that is sum of available ways to pick numbers, which summation is equal to k.

Remember to print \n at the end of output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

I'm a salary thief who don't answer students' question

~by anonymous TA

"I sucked!" TA think he's the worst, therefore he only asks you to do some cut and paste.

You got a string and your cursor is at the leftmost position of the string.

Let's call the leftmost position of the string position 0.

The string only contains character '1'~'3'.

You need to move the cursor to the right x times.

Each time only cross one character.

After the move, you divide the string into two part.

You cut the right part, and paste it for n times.

For n = the last character of left part of the string.

You need to answer how long the string is after x moves.

Because the string may be very long, you only need to answer the length of the final string mod 10^9+7(output positive number)

We guarantee that each move will not on empty character​. 

Example:

Given x = 5, string = "231"

Move 1(position 0->1):

cut the string "231" -> "2" and "31"

the last character of left part of the string = "2"

past "31" for 2 times, we got "23131"

Move 2(position 1->2):

cut the string "23131" -> "23" and "131"

the last character of left part of the string = "3"

past "131" for 3 times, we got "23131131131"

Move 3(position 2->3):

cut the string "23131131131" -> "231" and "31131131"

the last character of left part of the string = "1"

past "31131131" for 1 times, we got "23131131131"

Move 4(position 3->4):

cut the string "23131131131" -> "2313" and "1131131"

the last character of left part of the string = "3"

past "1131131" for 3 times, we got "2313113113111311311131131"

Move 5(position 4->5):

cut the string "2313113113111311311131131" -> "23131" and "13113111311311131131"

the last character of left part of the string = "1"

past "13113111311311131131" for 1 times, we got "2313113113111311311131131"

 

The final string "2313113113111311311131131" has length 25.

The answer will be 25%(10^9+7) = 25

Input

First line contains one integer t(1 <= t <= 10) which means the number of testcases.

Each testcase contains two lines.

First line contains one integer x(1 <= x <= 10^6)

Second line contains a string. ( 1 <= length of the string <= 500)

Output

For each testcase, print only one positive number which means the length of the final string mod 10^9+7

Remember to print \n at the end of output.

Sample Input  Download

Sample Output  Download

Tags

Discuss