All submissions for this problem are available.
This question is extremely easy. You just need to find the number of magical strings.
A string is called magical if it satisfies the following conditions.
1) Length of the string must be exactly N.
2) Each character of the string must be a lower case latin letter i.e. in ['a' - 'z'].
2) For each pair (L,R) in input, substring [L,R] of this string must be a palindrome.
First line contains T, the number of test cases.
For each test case, first line contains two integers, N - length of string and M - number of pairs [L,R].
Next M lines, each contains two integers [L,R].
Note : L and R are 1 based indexing of string.
For each test case, print the number of magical strings.
As the answer can be large, print it modulus 1000000007 (1e9 + 7).
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 2000
- 0 ≤ M ≤ 200000
- 1 ≤ L ≤ R ≤ N
|Tags||ipc151a, pigeonhole, skullcrackers, union-find|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.