Digital Clock

Time Limit : 5 sec, Memory Limit : 131072 KB

C: Digital Clock / デジタル時計

物語

あいずにゃんは最近,風邪を引いてしまった.あまりのだるさにベットから出られない.辛そうにしている姿もまたかわいい.

しかし暇で暇で仕方がないあいずにゃんは,枕下にあるデジタル時計で遊ぶ方法を考えついた.下の図のようなデジタル時計の光っている棒の本数を毎秒毎秒,ただひたすらに数えるのである.

何時間かこの遊びを続けた頃,あいずにゃんは時間が違っていても光っている棒の本数が等しい場合があることに気づいた.光っている棒の本数が等しい時間が何通りあるのか気になったあいずにゃんは,看病中のあなたに数えてくれるようお願いしてきた.

ベッドから出られないあいずにゃんのために,あなたはプログラムを書いて求めることにした.

問題

年月日,および時分秒を表示する上図のようなデジタル時計がある.光っている棒の本数がちょうど N 本になる年月日時分秒が何通りあるか答えよ.ただし,デジタル時計は一部壊れているため,絶対光らない棒が何箇所かある.光らない棒によって同じ表示に見える場合でも,表示しようとした年月日時分秒が異なる場合は別に数えることに注意せよ.

各数字の光る箇所は次の図に示す通りである.

デジタル時計は西暦を0詰め4桁(0000年〜9999年),月,日,時,分,秒をそれぞれ0詰め2桁で表示する.

月は1日から始まり,4, 6, 9, 11月は30日まで,1, 3, 5, 7, 8, 10, 12月は31日までである.2月は通常28日までだが,閏年には29日までとなる.ここで閏年とは,次のような年である.

  1. 西暦が400で割り切れる年は閏年である.
  2. 西暦が400で割り切れないが,100で割り切れる年は閏年ではない.
  3. 西暦が100で割り切れないが,4で割り切れる年は閏年である.
  4. 西暦が4で割り切れない年は閏年ではない.

時間は0時から23時まで,分は0分から59分まで,秒は0秒から59秒までである.閏秒に関しては考えなくてよい.

入力形式

1行目に光っている棒の本数 N (0 ≤ N ≤ 98) が与えられる.

2行目に壊れて光らない箇所の個数 K (0 ≤ K ≤ 98) が与えられ,続いて K 行に壊れている箇所の情報が与えられる.K 行のうち i 行目には,i 番目の壊れている棒の桁 p_i (0 ≤ p_i ≤ 13) と位置 q_i (0 ≤ q_i ≤ 6) が空白区切りで与えられる.

桁とは,次の図のようなデジタル時計の各数字に割り当てられたIDであり,上位の数字から順に0から13までを割り当てた番号のことである.

また,棒の位置とは次の図のような各数字中における棒のIDであり,上の棒から順に0から6までの数字を割り当てた番号のことである.

出力形式

光っている棒の本数がちょうど N 本になる年月日時分秒の総数を1行に出力せよ.

入力例1

28
0

出力例1

1

1111年11月11日11時11分11秒の1通りである.

入力例2

28
1
2 0

出力例2

2

1171年11月11日11時11分11秒 と 1111年11月11日11時11分11秒 の2通りである.

入力例3

98
1
3 0

出力例3

0

入力例4

60
1
3 0

出力例4

13362470370

Source: Ritsumeikan University Programming Camp 2015 , Problem set from Hokkaido University teams, Shiga, Japan, 2015-03-16