We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • HackerRank Home
  • |
  • Prepare
  • Certify
  • Compete
  • Apply
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Vim War

Vim War

Problem
Submissions
Leaderboard
Discussions
Editorial

A war has broken down between Vim and Emacs. Gedit, being Vim's ally, is captured by Emacs as a prisoner of war and it is up to Vim to rescue him by defeating Emacs.

For this task, Vim has to assemble an army of appropriate skills. He can choose a non-empty subset of soldiers from a set of soldiers (numbered from to ). Each soldier has some subset of skills out of different skills (numbered from to ). The skill-set of an army is the union of skill-sets of its constituent soldiers. To win the war, Vim needs to know how many different subsets of soldiers satisfy his skill-set requirement. Since the answer can be huge, print it modulo .

Note : The chosen army's skill-set must exactly match the skill-set requirement of Vim (i.e no extra skills must be present in the army's skill-set than what is required).

Input Format

The first line contains and , the number of soldiers to choose from and the number of different skills possible respectively.
The next lines contain boolean characters each. If the character of the line is , then the soldier possess the skill and if it is , then not.
The last line contains boolean characters denoting the requirement skill-set of Vim where the character being signifies that Vim wants the skill to be present in his final army and not, otherwise.

Constraints


Output Format

Output in a single line the required answer, as explained above.

Sample Input

4 2  
00  
10  
01  
11  
11  

Sample Output

10

Explanation

Vim wants both the skills to be present in his selected army. Hence, he can choose the following subsets of soldiers:

Author

viv001

Difficulty

Advanced

Max Score

120

Submitted By

1939

Need Help?


View discussions
View editorial
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits

Choose a translation


  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Helpdesk
  • Careers
  • Terms Of Service
  • Privacy Policy

Cookie support is required to access HackerRank

Seems like cookies are disabled on this browser, please enable them to open this website