# Mysterious For

问题描述 :

MatRush is an ACMer from ZJUT, and he always love to create some special programs. Here we will talk about one of his recent inventions.

This special program was called "Mysterious For", it was written in C++ language, and contain several simple for-loop instructions as many other programs. As an ACMer, you will often write some for-loop instructions like which is listed below when you are taking an ACM contest.

for (int i = 0; i < n; i++) {

for (int j = i; j < n; j++) {

for (int k = j; k < n; k++) {

blahblahblah();

}

}

}

Now, MatRush has designed m for-loop instructions in the "Mysterious For" program, and each for-loop variable was stored in an array a[], whose length is m.

The variable i represents a for-loop instructions is the i-th instruction of the "Mysterious For" program.There only two type of for-loop instructions will occur in MatRush’s "Mysterious For" program:

1-type: if a for-loop belongs to 1-type, it will be an instruction like this:

for (int a[i] = 0; a[i] < n; a[i]++) {

…

}

2-type: if a for-loop belongs to 2-type, it will be an instruction like this:

for (int a[i] = a[i - 1]; a[i] < n; a[i]++) {

…

}

In addition, after the deepest for-loop instruction there will be a function called HopeYouCanACIt(), here is what’s inside:

void HopeYouCanACIt() {

puts("Bazinga!");

}

So, the "Mysterious For" program, obviously, will only print some line of the saying: "Bazinga!", as it designed for.

For example, we can assume that n equals to 3, and if the program has three 1-type for-loop instructions, then it will run 33=27 times of the function HopeYouCanACIt(), so you will get 27 "Bazinga!" in total. But if the program has one 1-type for-loop instruction followed by two 2-type for-loop instructions, then it will run 3+2+1+2+1+1=10 times of that function, so there will be 10 "Bazinga!" on the screen.

Now MatRush has the loop length n and m loop instructions with certain type, then he want to know how many "Bazinga!" will appear on the screen, can you help him? The answer is too big sometimes, so you just only to tell him the answer mod his QQ number:364875103.

All for-loop instructions are surely nested. Besides, MatRush guaranteed that the first one belongs to the 1-type. That is to say, you can make sure that this program is always valid and finite. There are at most 15 1-type for-loop instructions in each program.

输入:

First, there is an integer T(T<=50), the number of test cases.

For every case, there are 2 lines.

The first line is two integer n(1<=n<=1000000) and m(1<=m<=100000) as described above.

The second line first comes an integer k(1<=k<=15), represents the number of 1-type loop instructions, then follows k distinctive numbers, each number is the i-th 1-type loop instruction’s index(started from 0), you can assume the first one of this k numbers is 0 and all numbers are ascending.

All none 1-type loop instructions of these m one belongs to 2-type.

输出:

First, there is an integer T(T<=50), the number of test cases.

For every case, there are 2 lines.

The first line is two integer n(1<=n<=1000000) and m(1<=m<=100000) as described above.

The second line first comes an integer k(1<=k<=15), represents the number of 1-type loop instructions, then follows k distinctive numbers, each number is the i-th 1-type loop instruction’s index(started from 0), you can assume the first one of this k numbers is 0 and all numbers are ascending.

All none 1-type loop instructions of these m one belongs to 2-type.

样例输入:

5

3 3

3 0 1 2

3 3

1 0

3 3

2 0 2

4 4

4 0 1 2 3

10 10

10 0 1 2 3 4 5 6 7 8 9

样例输出:

Case #1: 27

Case #2: 10

Case #3: 18

Case #4: 256

Case #5: 148372219

- 点赞
- 写回答
- 关注问题
- 收藏
- 复制链接分享
- 邀请回答

*1*条回答

#### 为你推荐

- 去os.Truncate（）不重置文件光标
- IT行业问题
- 计算机技术
- it技术
- 编程语言问答
- 互联网问答
- 1个回答

- net / http.Request.URL.Host返回空字符串
- url
- request
- http
- 2个回答

- 注册表格电子邮件验证[关闭]
- php
- javascript
- login
- 2个回答

- 为什么传递给PHP的cookie或数据字符串中缺少“+”字符，如何更正此问题
- string
- cookies
- character-encoding
- php
- 1个回答

- 如何推送网站内容并在顶部插入广告？
- php
- html
- javascript
- 3个回答

- Array_push（）在for循环中不起作用
- php
- 2个回答

- 请问这里的求第n个配对的整数，使用C语言怎么计算？思路不太会
- Little Tiger vs. Deep Monkey
- Yong Zheng's Death
- string
- each
- lines
- it
- 1个回答

- Mysterious For
- acm
- c++
- 函数
- equals
- 1个回答

- The Best Travel Design
- acm
- velocity
- path
- 2个回答

- zz's Mysterious Present
- each
- 1个回答

- Palace
- lines
- 1个回答

- Mystery
- it
- 1个回答

- Dreisam Equations
- less
- 1个回答

- In Action
- 网络
- 1个回答

- Mysterious Mountain
- Golang
- 2个回答

- The mysterious X network
- something
- 1个回答

- Door Repairing
- as
- 1个回答