TopCoder

User's AC Ratio

100.0% (12/12)

Submission's AC Ratio

51.4% (18/35)

Description

“唔 ~ 啊 啊 啊 啊 啊 啊!!!!!!”
妁艷爸爸大吼著,他被妤嬌的攻擊命中了!!!
“父親...你為甚麼要這麼做"妁艷妹妹看著躺在地上的爸爸,呢喃著說...
“事不遲疑,快去救出妁艷吧"剝剝火姬說著
“來~ 走吧~ 事情一定會水落石出的~"妤嬌姐姐拉著妁艷妹妹說
妤嬌一行人走到了祭壇的頂端,打開了門,看見了被綁住的妁艷
“哥哥~~~我好想你~~~”妁艷妹妹哭著喊
“你再不回地球,你的微積分就要被當掉了喔哈哈”妤嬌冷冷的說
“快把我放開啦囧”妁艷說著 妁艷身上有好幾把鎖把妁艷鎖著
每把鎖上都有 $2\times N$ 個點,排成矩形的樣子,左右長為 $N$,上下寬為 $2$,左右、上 下兩點之間距離都一樣。而最左邊還有一個點為起點,最右邊有一個點為終點。 現在希望能從起點畫到終點,並能經過所有的點。
不過還有三個條件:
1.當上面那排點由左到右是由 $X_1$ 到 $X_N$、下面那排由左到右是 $Y_1$ 到 $Y_N$ 時,起點只 能畫到 $X_1$ 或 $Y_1$,且只有 $X_N$ 和 $Y_N$ 能畫到終點。
2.當$ X_1$ 到 $X_i$ 還沒全部畫到前,不可以畫 $X_{i+1}$, $Y$ 也一樣
3.可以由 $X_{i+1}$ 畫到 $Y_i$ 或 $Y_{i+1}$ 畫到 $X_i$,即是可以畫到另一排的前一個,但兩個以上 則不行
另外還有三個數 $A$、$B$、$C$ 代表在 $X,Y$ 兩排之間前進、後退畫時所需的時間
(代表從起點出來或出去到終點皆不用算)
$A$ 代表畫斜率為$ 0 $的線時所需的時間
$B$代表畫斜率為 $1$ 的線時所需的時間
$C$ 代表畫斜率為$-1$ 的線時所需的時間 請你把妁艷放開吧~

$N=5$ 其中一種

時間:$4A+2B$

Input Format

第一行會有一個正整數 $T$ 代表有$ T$ 把鎖要解
接下來會有$2T$ 行,代表 $T$ 把鎖的資料
每一把鎖的第一行會有一個正整數 $N$ 代表鎖的長度
第二行則有三個正整數 $A$、$B$、$C$ 如題目所述

對$100\%$的測資 $T\leq 10$;
對$10\%$的測資 $N\leq 5$;
對$30\%$的測資 $N\leq 10^ {2}$;
對$50\%$的測資 $N\leq 10^ {6}$;
對$70\%$的測資 $N\leq 10^ {7}$;
對$100\%$的測資 $N\leq 10^ {18}$;
對$100\%$的測資 $A, B, C \leq10$.

Output Format

對於每一把鎖輸出兩行
第一行輸出有幾種解法
第二行輸出若畫出所有解法共需的時間為多少
答案太大請$\mod 1000000007$

Sample Input

Sample Input 1:
1
1
1 1 1

Sample Input 2:
2
5
1 1 1
5
1 2 1

Sample Output

Sample Output 1:
2
0

Sample Output 2:
120
704
120
852

Hints

妤嬌把鎖住妁艷的鎖解開了,妁艷便和妤嬌、妁艷妹妹、妤嬌姐姐、剝剝火姬搭 乘太空船,準備返回地球了......
就在他們冥王星起飛後,只見妁艷爸爸要舉起那把改造武器,瞄向太空船,準備 把他們打下來!!!
“妁艷,別想給我走!!!”妁艷爸爸吼著
“不要啊~~~”妁艷妹妹說
“不!父親!!!那武器不能那樣用啊!!!!!!那樣操作會完蛋啊!!!”妁艷大吼著!!!
只見妁艷父親按下了開關,那武器就發出了極大的攻擊......
妁艷等人在太空船上回頭看,只見冥王星被白霧覆蓋著,
白霧消去後,太空中空空的,冥王星已不存在了,而妁艷父親就這樣消失了.......

Problem Source

原TIOJ1792 / problem: lnsuyn; source: TOI 2010 3模
Added $\LaTeX$ by Seanliu on 20201103

Subtasks

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3
3 1000 65536 262144 4
4 1000 65536 262144 5
5 1000 65536 262144 6
6 1000 65536 262144 7
7 1000 65536 262144 8
8 1000 65536 262144 9
9 1000 65536 262144 10