We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Mathematics
  3. Combinatorics
  4. Anti-Palindromic Strings

Anti-Palindromic Strings

Problem
Submissions
Leaderboard
Discussions
Editorial

You are given two integers, and . Count the number of strings of length (under the alphabet set of size ) that doesn't contain any palindromic string of the length greater than as a consecutive substring.

Input Format

Several test cases will be given to you in a single file. The first line of the input will contain a single integer, , the number of test cases.

Then there will be lines, each containing two space-separated integers, and , denoting a single test case. The meanings of and are described in the Problem Statement above.

Output Format

For each test case, output a single integer - the answer to the corresponding test case. This number can be huge, so output it modulo .

Constraints


Sample Input

2
2 2
2 3

Sample Output

2
6

Explanation

For the 1st testcase, we have an alphabet of size M = 2. For the sake of simplicity, let's consider the alphabet as [A, B]. We can construct four strings of size N = 2 using these letters.

AA
AB
BA
BB

Out of these, we have two strings, AB and BA, that satisfy the condition of not having a palindromic string of length greater than 1. Hence, the answer 2.

For the 2nd test case, we have an alphabet of size M = 3. For the sake of simplicity, let's consider the alphabet as [A, B, C]. We can construct nine strings of size N = 2 using these letters.

AA
AB
AC
BA
BB
BC
CA
CB
CC

Save AA, BB, and CC, all the strings satisfy the given condition; hence, the answer 6.

Author

zxqfd555

Difficulty

Medium

Max Score

50

Submitted By

1982

Need Help?


View discussions
View editorial
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits

Choose a translation


  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature