Background
The DSA (Digital Signature Algorithm) is a publickey cryptographic algorithm for creating digital signatures. The signature is created secretly but can be verified publicly. This means that only one subject can create a signature, but anyone can verify its correctness. The algorithm is based on the computational complexity of taking logarithms in finite fields.
The first phase of key generation is a choice of algorithm parameters which may be shared between different users of the system.
 Decide on a key length L and N. This is the primary measure of the cryptographic strength of the key. The minimal recommended values for L and N are 1024 and 160.
 Choose an approved cryptographic hash function H (for example SHA2). The hash output must be an Nbit integer.
 Choose an Nbit prime q.
 Choose an Lbit prime modulus p such that p − 1 is a multiple of q.
 Choose g, a number whose multiplicative order modulo p is q. This may be done by setting g = h ^{(p − 1) / q} mod p for some arbitrary h (1 < h < p − 1), and trying again with a different h if the result comes out as 1. Most choices of h will lead to a usable g; commonly h = 2 is used.
Given a set of parameters, the second phase computes private and public keys for a single user:
 Choose x by some random method, where 0 < x < q.
 Calculate y = g ^{x} mod p.
 Public key is (p, q, g, y). Private key is x.
Let m be the message and H(m) the hash value of that message.
 Generate a random permessage number k where 0 < k < q.
 Calculate r = (g^{k} mod p) mod q.
 In the unlikely case that r = 0, start again with a different random k.
 Calculate s = k^{−1}(H(m) + x ∙ r) mod q.
 In the unlikely case that s = 0, start again with a different random k.
 The signature is (r, s).
 Reject the signature if 0 < r < q or 0 < s < q is not satisfied.
 Calculate w = s^{−1} mod q.
 Calculate u_{1} = H(m) ∙ w mod q.
 Calculate u_{2} = r ∙ w mod q.
 Calculate v = ((g^{u1} ∙ y^{u2}) mod p) mod q.
 The signature is valid if v = r.
Problem
Given the public key (q, p, g, y) and the hash value of the message H(m) you are to create a valid signature (r, s).
Input
The only line contains integers N, L, q, p, g, y, H(m). The following limitations are applied:
 3 ≤ N ≤ 36;
 6 ≤ L ≤ 60; L ≥ N + 3;
 q is an exactly Nbit integer;
 p is an exactly Lbit integer;
 1 < g < p;
 0 ≤ y < p;
 H(m) is an Nbit integer.
The public key is guaranteed to be generated as described above.
Output
Output the integers r and s separated with space. The pair (r, s) must be a valid DSA signature for the public key (q, p, g, y). There are multiple valid signatures, you may output any of them.
Sample
input  output 

3 6 5 41 10 16 2
 3 3

Problem Author: Prepared by Vladimir Yakovlev. Text by Wikipedia, the free encyclopedia.