F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

Necklace of Beads

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 362    Accepted Submission(s): 163


Problem Description
Beads of red, blue or green colors are connected together into a circular necklace of \(n\) beads. If the repetitions that are produced by rotation around the center of the circular necklace are all neglected, the green beads appear no more than \(k\) times, and all adjacent beads are of different colors, how many different forms of the necklace are there?
 

Input
The first line contains an integer \( T(1\le T\le 10) \)representing the number of test cases.

For each test case, there are two integers \(n,k(3\le n\le 10^6,0\le k\le 10^6) \)in one line.

It is guaranteed that \(\sum n,\sum k < 5*10^6\).
 

Output
For each test case, print a line with an integer, representing the answer, modulo \(998244353\).
 

Sample Input
3 3 1 4 1 10 3
 

Sample Output
2 3 58
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-03-29 10:11:54, Gzip enabled