咳咳咳，这几天有人叫我发一点有难度的题

那就如你们所愿！！！

今天的题目是 计蒜客 里面的题！！！来挑战一下吧！！！

——网上有题解，相信你们不用题解也会写出来的！！！

蒜头君的兔子

蒜头君的小伙伴在 第一年 送给他一对一岁的兔子，

并告诉他：这种兔子 刚生下来时算 0 岁，到2岁时就可以繁殖了，

它在 2到10 岁时，每年会生下来一对兔子，这些兔子到了2岁也可以繁殖，

但这些兔子在 10岁那年 生完仔后 不久就会死亡，

蒜头君想知道，第n 年兔子 产仔之后（第 n 年 10 岁的兔子此时已经死亡），

他会有多少对兔子。结果对1000000007 取模。

输入格式

共一行，一个正整数 n，表示蒜头君想知道第 n年的兔子总对数。

输出格式

输出一个整数，表示第 n 年兔子总对数对1000000007 取模的值。

数据规模

对于 30% 的数据，满足 1<=n<=1000

对于 60% 的数据，满足 1<=n<=100000

对于100% 的数据，满足 1<=n<=1000000000

样例输入1

10

样例输出1

88

样例输入2

88

样例输出2

352138150

样例输入3

10086

样例输出3

405567313

蒜头君的排序

蒜头君是一个爱思考的好孩子，这一天他学习了冒泡排序，

于是他就想，把一个乱序排列通过冒泡排序排至升序需要多少次交换，

这当然难不倒他，于是他想来点刺激的，给定一个 1 \ldots n1…n 的排列，

每次从该排列中选择一个区间 [l,r][l,r]，问使用冒泡排序将该区间排至升序需要多少次交换操作。

输入格式

第一行一个整数 n，表示排列长度。

接下来一行 n 个整数，表示该排列。

接下来一行一个整数 m，表示询问次数。

接下来 m 行，每行 2 个整数 l,rl,r，表示询问 [l,r] 区间。

输出格式

输出 m 行，每行 1 个整数，第 ii 行表示第 i个询问的答案。

数据规模

样例输入

10

9 8 7 4 5 6 10 3 2 1

5

2 4

8 10

2 8

5 9

4 9

样例输出

3

3

13

7

9

蒜头君救人

蒜头君是一个乐于助人的好孩子，这天他所在的乡村发生了洪水，

有多名村民被困于孤岛上，于是蒜头君决定去背他们离开困境，

假设蒜头君所在的村子是  n*m 的网格，

网格中.号代表平地，#号代表该地已被洪水淹没，

A、B……等大写字母表示该地有村民被困，

s代表蒜头君的起点，t代表蒜头君的终点。

蒜头君的初始速度为 k 秒一格，他每次可以向上下左右 4 个方向中的一个移动 1 格。

在背上一个村民后，他的速度可能会降低，也可能会加快，但他的速度不能快于 1 秒每格，

那么蒜头君想知道，他最快需要多长时间将所有村民救出？

注意：不能在终点以外的地方放下村民；可以同时背多个村民。

输入格式

第一行 3 个正整数 n,m,k分别表示村庄长度、宽度、蒜头君初始速度。

接下来 n 行，每行一个长度为 m 的字符串，表示村庄的地形，字符串意义如上所述。

接下来若干行，每行一个大写字母、一个整数，表示该编号的村民会使 k增加 / 减少多少。行数等同于地形中大写字母的个数。

大写字母按字典序，即A、B、C的顺序排列，保证前后两行的字母是连续的。

输出格式

输出 11 个整数，表示最小用时。

数据规模

对于 10% 的数据，满足 1 \le n,m \le 51≤n,m≤5，村民个数为 1；

对于 50% 的数据，满足 1\le n,m\le51≤n,m≤5，村民个数小于等于 5；

对于 100% 的数据，满足 1\le n,m\le101≤n,m≤10，村民个数小于等于 10。

样例输入

4 4 2

s.##

..A#

.B##

...t

A -3

B 4

样例输出

17

做完后请在评论区留言，交流算法！！！